задача про рюкзак

Тема в разделе "Общие вопросы по С и С++", создана пользователем biv171, 27 мар 2009.

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

    biv171 Гость

    ребят если можете помогите плиз,я тока начал(пытаюсь) программировать на С и столкнулся вот с чем,задача у меня про рюкзак,решаю я эту задачу с помощью наивного алгоритма , т.е перебираю все возможные варианты так если вещей 3 ,то 001,010,011,100,101,110,111..вроде как все компилируется,а ответ неправильный(в коде я вроде как уверен все логично)т.е например:нам дан максимальный вес 6 кг вещей у нас три : 1кг ,2кг, 3кг т.е ответ д/б [1 1 1]..

    подскажите пожайлуста где я еще накосячил???
    Код (Text):
    #include <stdio.h>
    #include <stdlib.h >

    void prt(int n,int s);


    int main()
    {
    int i,a[20],s,n;

    printf("Vvedite kolichestvo elementov= ");
    scanf("%d",&n);

    printf ("vvedite elementi a[i]: ");
    for(i=1;i<=n;++i)
    scanf("%d",&a[i]);
    //for (i=1;i<n;++i)
    //  printf("%d",a[i]);

    printf("vvedite symmy S= ");
    scanf("%d",&s);

    prt(n,s);


    }

    void prt(int n,int s)
    {
    int flag,sum,p,i,j;
    int a[20];
    int e[20];
    int ans[20][20];

    flag=0;
    for(i=1;i<n;++i)
    e[i]=0;
    p=0;
    while (flag==0) {
    i=1;
    if (e[i]==0)
    e[i]=1;
    else {
    while (e[i]==1) {
    e[i]=0;
    ++i;
    }

    e[i]=1;
    }

    flag=1;
    for(j=1;j<n;++j) {
    flag=e[j]*flag;
    }

    sum=0;
    for(j=1;j<n;++j)
    sum=a[j]*e[j] + sum;
    if (s==sum) {
    ++p;
    for(j=1;j<n;++j)
    ans[p][j]=e[j];
    }
    }

    if (p>0){
    for(j=1;j<p;++j)
    {
    printf("[");
    for(i=1;i<n;++i)
    printf( "%d",ans[j][i]);
    printf("]\n");
    }
    }
    else printf("net reshenia\n");

    }
     
  2. Dimmuborgir

    Dimmuborgir Гость

    если чесно, я не понял что надо найти. но могу сказать точно что будет полная попа если ввести n=21 или больше).
     
  3. biv171

    biv171 Гость

    хорошо,задано:
    1)s=6кг -максимальный вес который мы можем взять.
    2)массив a -данный массив содержит количество вещей и их вес,так например n=3 -количество вещей ,а элементы массива a их вес например первая вещь 1кг,вторая вещь 2кг,третья 3 кг. Т.е мы имеем массив a который "условно"выглядит так: [1,2,3]
    Найти:
    используя наивный алгоритм(перебором всех решений) найти решение,т.е т.к. у нас 3 вещи =>мы можем иметь 7 предполагаемых "вариантов-решений" (массив e=(001,010,011,100,101,110,111) и дальше перебором всех вариантов мы и занимаемся ,т.е:
    1ый вариант: e=[0,0,1] и a=[1,2,3] => e*a=0*1+0*2+0*3=0, пото сравниваем равно ли это нашему максимальному весу т.е 6 кг нет не ровно значит это не решение...
    2ой вариант: e=[0,1,0] и a=[1,2,3]=.e*a=...=2 => 2 не равно 6 -это не решение
    3ий вариант....[0,1,1]....будет равно 5 -это тоже не решение
    .....
    и так проходим каждый вектор (001,010,011,100,101,110,111) решением задачт будет как раз этот вектор
    в данном случае решением является вектор

    [1,1,1]-вот что должно появится в конце!
    надеюсь обьяснил понятно?

    естественно вещей может быть и двадцать ,3 вещи я взял для простоты!
     
  4. Vadik(R)

    Vadik(R) Well-Known Member

    Регистрация:
    12 дек 2007
    Сообщения:
    483
    Симпатии:
    0
    Делай трассировку, больше ничего не могу сказать. Да, задачи на динамическое программирование тем и сложны, что поначалу надо придумать характеристику какого-то состояния, написать программу, а потом искать косяки :)
     
Загрузка...
Статус темы:
Закрыта.

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