Помогите с СРР

Тема в разделе "Общие вопросы по С и С++", создана пользователем Guest_, 26 июл 2005.

Статус темы:
Закрыта.
  1. Guest_

    Guest_ Гость

    У меня такая проблема:
    есть переменные например
    a
    b
    c
    d
    ...
    Каждая из них имеет значение. Необходим алгоритм который бы высчитывал комбинации переменных максимально приближенные к 1030.
    Например:
    a=300
    b=550
    c=460
    d=580
    максимально приближенный вариант (в порядке убывания) b,c; d,a; c,a
    ---------------------------------------------------------------------------------------------
    Если кто знает подскажите плз, сроки горят, а сам я не волшебник только учусь.
     
  2. Guest_Bapbap_*

    Guest_Bapbap_* Гость

    <!--QuoteBegin-Guest_Олег_*+26:07:2005, 14:27 -->
    <span class="vbquote">(Guest_Олег_* @ 26:07:2005, 14:27 )</span><!--QuoteEBegin-->У меня такая проблема:
    есть переменные например
    a
    b
    c
    d
    ...
    Каждая из них имеет значение. Необходим алгоритм который бы высчитывал комбинации переменных максимально приближенные к 1030.
    Например:
    a=300
    b=550
    c=460
    d=580
    максимально приближенный вариант (в порядке убывания) b,c; d,a; c,a
    ---------------------------------------------------------------------------------------------
    Если кто знает подскажите плз, сроки горят, а сам я не волшебник только учусь.
    [snapback]22578" rel="nofollow" target="_blank[/snapback]​
    [/quote]
    Тут попахивает генетическими алгоритмами. Выложи подробный текст задачи.
     
  3. ????

    ???? Гость

    Для: Guest_Bapbap_*
    А как мне кажется - простая сортировка всех возможных сумм. Только нужны полные условия. Кол-во переменных, откуда берутся (вводятся или заданы), что делать если сумма > 1030, если есть суммы 1040 и 1020 какую считать более близкой...
     
  4. Guest

    Guest Гость

    Писал я что-то подобное, только там было немного сложнее, там были даны n1 чисел a, n2 чисел b и т. д. Решение искал перебором. Вот исходники, рабочие, если только это последние версии. Только как она работает не помню.

    main.c

    //если переполнение стека, то файл вывода пустой

    #include <stdio.h>
    #include <stdlib.h>
    #include <memory.h>
    #include <string.h>

    //i-index s-size n-number

    #define SARESULT 10

    extern int timeout;
    void inittimer(int ilimtime);
    void destroytimer(void);

    int t;
    long lim;//максимальная сумма aresult[j] по j
    long sum;//подбираемая сумма
    long *acost;
    long sacost;//размер массива цен, будет вводиться; не выходит за size_t
    long *anumber;
    long **aaresult;//массив вариантов подбора
    long saresult = SARESULT;
    long *aresult;//вариант подбора

    long nresult = 0;//количество вариантов подбора, 0 < nresult <= SARESULT
    long gdif = 4335;//текущая разность между sum и подобранной суммой

    void perebor(long iacost, long ngood, long dif);
    void saveresult(long dif);
    void addresult(void);
    void erase(void);
    void outaaresult(void);
    int inputdata(void);

    main()
    {
    if(!inputdata()){
    printf("error input");
    return 1;
    }
    inittimer(t);
    perebor(0, 0, sum);
    destroytimer();
    outaaresult();
    return 0;
    }

    //iacost - индекс подбираемой цены
    //ngood - уже подобранное количество товара
    //dif - оставшаяся к подбору сумма
    void perebor(long iacost, long ngood, long dif)
    {
    if(timeout)
    return;
    if(iacost == sacost){
    //подбор закончен
    saveresult(dif);
    return;
    }
    aresult[iacost] = __min(dif / acost[iacost], __min(lim - ngood, anumber[iacost]));
    for(;aresult[iacost] >= 0; aresult[iacost]--)
    perebor(iacost + 1, ngood + aresult[iacost], dif - aresult[iacost] * acost[iacost]);
    }

    void saveresult(long dif)
    {
    if(gdif < dif)
    return;
    if(gdif == dif){
    addresult();
    return;
    }
    erase();
    addresult();
    gdif = dif;
    }

    void erase(void)
    {
    nresult = 0;
    }

    void addresult(void)
    {
    if(nresult < saresult){
    memcpy(aaresult[nresult], aresult, sizeof(long) * (size_t)sacost);
    nresult++;
    }
    }

    void outaaresult(void)
    {
    long iaaresult1, iaaresult2;

    #ifdef _DEBUG
    printf("dif=%li\n", gdif);
    printf("nresult=%li\n", nresult);
    #endif
    for(iaaresult1 = 0; iaaresult1 < nresult; iaaresult1++){
    for(iaaresult2 = 0; iaaresult2 < sacost; iaaresult2++)
    printf("%li ", aaresult[iaaresult1][iaaresult2]);
    printf("\n");
    }
    #ifdef _DEBUG
    {
    long iacost;
    for(iacost = 0; iacost < sacost; iacost++)
    printf("%li\n", acost[iacost]);
    for(iacost = 0; iacost < sacost; iacost++)
    printf("%li\n", anumber[iacost]);
    }
    #endif
    }

    int inputdata(void)
    {
    //для распределения памяти
    //sizeof(long) * (size_t)sacost и
    //sizeof(long*) * (size_t)SARESULT
    //должно вмещаться в тип size_t
    long iacost, ianumber;
    long iaaresult1;

    scanf("t=%i", &t);
    getchar();
    scanf("lim=%li", &lim);
    getchar();
    scanf("sum=%li", &sum);
    getchar();
    scanf("sacost=%li", &sacost);
    getchar();
    if(sacost > 60000)
    return 0;
    acost = malloc(sizeof(long) * (size_t)sacost);
    if(acost == NULL)
    return 0;
    scanf("acost=");
    getchar();
    for(iacost = 0; iacost < sacost; iacost++)
    scanf("%li", acost + iacost);
    getchar();
    anumber = malloc(sizeof(long) * (size_t)sacost);
    if(anumber == NULL)
    return 0;
    scanf("anumber=");
    getchar();
    for(ianumber = 0; ianumber < sacost; ianumber++)
    scanf("%li", anumber + ianumber);
    getchar();
    aaresult = malloc(sizeof(long*) * (size_t)SARESULT);
    if(aaresult == NULL)
    return 0;
    for(iaaresult1 = 0; iaaresult1 < SARESULT; iaaresult1++){
    aaresult[iaaresult1] = malloc(sizeof(long) * (size_t)sacost);
    if(aaresult[iaaresult1] == NULL)
    return 0;
    }
    aresult = malloc(sizeof(long) * (size_t)sacost);
    if(aresult == NULL)
    return 0;
    return 1;
    }

    time.c


    #include <dos.h>
    #include <stdio.h>

    int timeout;
    int timeis;//17 times per second
    int limtime;

    //ih-interrupt handler
    //p-pointer

    void (__interrupt __far *pihold)();
    void __interrupt __far ihnew();

    void inittimer(int ilimtime)
    {
    timeout = 0;
    timeis = 0;
    limtime = ilimtime * 17;
    pihold = _dos_getvect(8);
    _dos_setvect(8, ihnew);
    }

    void destroytimer(void)
    {
    _dos_setvect(8, pihold);
    #ifdef _DEBUG
    printf("t=%i\n", timeis);
    #endif
    }

    void __interrupt __far ihnew()
    {
    timeis++;
    if(timeis == limtime)
    timeout = 1;

    }
     
  5. alam

    alam Гость

    Забыл подписаться ;)
     
  6. DAle

    DAle Гость

    <!--QuoteBegin-Guest_Олег_*+26:07:2005, 14:27 -->
    <span class="vbquote">(Guest_Олег_* @ 26:07:2005, 14:27 )</span><!--QuoteEBegin-->У меня такая проблема:
    есть переменные например
    a
    b
    c
    d
    ...
    Каждая из них имеет значение. Необходим алгоритм который бы высчитывал комбинации переменных максимально приближенные к 1030.
    Например:
    a=300
    b=550
    c=460
    d=580
    максимально приближенный вариант (в порядке убывания) b,c; d,a; c,a
    ---------------------------------------------------------------------------------------------
    Если кто знает подскажите плз, сроки горят, а сам я не волшебник только учусь.
    [snapback]22578" rel="nofollow" target="_blank[/snapback]​
    [/quote]

    Если необходимо вывести все возможные варианты в порядке убывания близости, то решается обычным перебором. Если необходимо константное количество наиболее близких вариантов, переменные натуральные и есть возможность использовать O(s) памяти, то решается с помощью динамического программирования.

    P.S. Про генетические алгоритмы клево, лежал под столом.
     
  7. alam

    alam Гость

    А можно поподробнее?
    Насколько я знаю первый шаг в динамическом программировании - разбиение на подзадачи. А как эту задачу разбить на подзадачи?
     
  8. DAle

    DAle Гость

    Все достаточно просто. Рекуррентное соотношение выглядит следующим образом (A - i-ый элемент):
    Код (Text):
    F(i,k) = 0, если k < 0
    F(0,0) = 1
    F(i,k) = max(F(i-1,k), F(i-1,k-A[i]))
    Значение F(i, k) будет равно 1, если с помощью первых i элементов можно построить сумму k. Реализовывается нахождение значений функции с помощью одномерного массива, который пересчитывается на каждой итерации. Для исходной задачи достаточно будет строить значения функции для величины второго параметра <= 2*s. Затем, после нахождения всех F(n,k), где n - количество элементов, достаточно найти ближайщую к s единицу. Как восстановить слагаемые, думаю, понятно.

    P.S. Эта задача рассматривается, если не ошибаюсь, в книжке для 10-11 классов <_<
     
Загрузка...
Статус темы:
Закрыта.

Поделиться этой страницей