Здравствуйте, Titanik0, Вы писали:

T>

T>         t1=c[i]+Rec(pos+1,t);         
T>

Здесь должно быть не pos+1, а i+1.

Здравствуйте.
Хочу решить задачу о рюкзаке 0\1(по англоязычной литературе) — то есть при условии что каждый предмет нужно брать лишь раз. Интересует рекурсивный алгоритм.
Нашел такое решение :

int knap(int i,int cost,int weight){
   if (i>=N) return cost; else
    {
      int t1=knap(i+1,cost,weight);
      int t2=0;
      if ((weight+w[i])<=W){
          t2=knap(i+1,cost+c[i],weight+w[i]);
      }
      if (t1>t2) return t1; else return t2;
    }
}

Тут два вызова функции самой себя. Решил написать с одним. Имею:

int Rec(int pos,int wt){
   int max=0;   
   int t1=0;
   for(int i=pos;i<N;i++){
      int t=wt-w[i];
      if (t>=0){           
         t1=c[i]+Rec(pos+1,t);         
         if (t1>max) max=t1;
      } 
   }
   
   return max;
}

Имхо вполне очевидно все. НО. Сумма возвращается неверная — то есть скажем так, до определенного момента, возврат был верен и значения максимальной стоимости в переменной max накапливались правильно. Но поднимаясь из рекурсии, — в самом конце начали искажаться в большую сторону. Где-то есть ошибка, — первое предположение. Но , возможно, с помощью одного рекурсивного вызова невозможно эту задачу решить именно при условии включении не больше одного предмета. У кого какие предположения?

Здравствуйте, Titanik0, Вы писали:

Ошибку уже назвали, методическое замечание.

T>Тут два вызова функции самой себя. Решил написать с одним.

Тут не один вызов, тут вызов в цикле. В принципе выполняет тот же объем работы, что и первый вариант, за исключением того, что добавлено отсечение варианта брать вещь, когда она уже не лезет в рюкзак, на ранней стадии (в первом варианте первая ветка без такой проверки).

Радикально было бы переписать это вообще без рекурсии. Могёшь?

а вам не кажется что сложность алгоритма из 2^n превратили в n! ?

Здравствуйте, subdmitry, Вы писали:

S> В принципе выполняет тот же объем работы, что и первый вариант, за исключением того, что добавлено отсечение варианта брать вещь, когда она уже не лезет в рюкзак, на ранней стадии (в первом варианте первая ветка без такой проверки).
Тьфу, а там и не нужна такая проверка.

Тут кажется еще одна ошибка:

T> int t=wt-w[i];
T> if (t>=0){
T> t1=c[i]+Rec(pos+1,t);

Вместо c[i] вроде должно быть w[i] (если это не две копии одного и того же массива ).

Здравствуйте, subdmitry, Вы писали:

S>Радикально было бы переписать это вообще без рекурсии. Могёшь?

И че все так не любят рекурсию?) Она же элегантнее. Сравни:

int getMaxRecursive(int pos,int capacity)
{
    if(pos == N)
    {
        return 0;
    }
    int res = getMaxRecursive(pos + 1, capacity);
    if(capacity >= weight[pos])
    {
        res = max(res, getMaxRecursive(pos + 1, capacity - weight[pos]) + cost[pos]);
    }
    return res;
}

И

int getMaxIterative()
{
    int res = 0;
    for(int i = 0; i < (1<<N); i++)
    {
        int curCost = 0;
        int curWeight = 0;
        for(int j = 0; j < N; j++)
        {
            if(i & (1<<j))
            {
                curCost += cost[j];
                curWeight += weight[j];
            }
        }
        if(curWeight <= maxWeight && curCost > res)
        {
            res = curCost;
        }
    }
    return res;
}

ИМХО первый вариант значительно красивее второго.

Здравствуйте, Mace, Вы писали:

S>>Радикально было бы переписать это вообще без рекурсии. Могёшь?

M>И че все так не любят рекурсию?) Она же элегантнее. Сравни:

С рекурсией элегантнее, но медленее. Даже лобовой вариант расписывания рекурсии через использование стека данных должно быть быстрее. Правда, заниматься такими неалгоритмическими оптимизациями имеет смысл далеко не всегда.

Здравствуйте, subdmitry, Вы писали:

S>Вместо c[i] вроде должно быть w[i]

Блин, чего же меня сегодня так глючит. Все было правильно написано.

Здравствуйте, Vintik_69, Вы писали:

V_>Здравствуйте, Titanik0, Вы писали:

T>>

T>>         t1=c[i]+Rec(pos+1,t);         
T>>

V_>Здесь должно быть не pos+1, а i+1.
Все, понял свою ошибку . Огромное спасибо!