Здравствуйте.
Хочу решить задачу о рюкзаке 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 накапливались правильно. Но поднимаясь из рекурсии, — в самом конце начали искажаться в большую сторону. Где-то есть ошибка, — первое предположение. Но , возможно, с помощью одного рекурсивного вызова невозможно эту задачу решить именно при условии включении не больше одного предмета. У кого какие предположения?