Проблема с рюкзаком - найдите, какие вещи взяты

Question

Мне нужно найти оптимальное решение для рюкзака. Вот мой код

void knapSack(int W, int wt[], int val[], int n)
{
   int i, w;
   int K[W+1][n+1];
   for (w = 0; w <= W; w++)
   {
    for(i=0;i<=n;i++){
        if(i==0)
            K[w][i]=0;

        if(w<wt[i-1] && i!=0)
            K[w][i]=K[w][i-1];

        if(w>=wt[i-1] && i!=0)
            K[w][i]=max(K[w][i-1],K[w-wt[i-1]][i-1]+val[i-1]);

       }
   }

   i=n;
  int j=W;
   while(i,j>0){
    if(K[j][i]!=K[j][i-1]){
        cout<<"Item "<<i<<" is in the bag"<<endl;
        i=i-1;
        j=j-wt[i-1];
    }
    else
        i=i-1;
   }
}

Входные данные:

4 6 //n W
2 1 //p1 w1
3 2 //p2 w2
3 4 //p3 w3
4 5 //p4 w4

И вывод должен быть таким:

1 4
2 3

Первая часть моего кода, которая упаковывает сумку, работает отлично, но вторая часть, где я пытаюсь выяснить, какие предметы были взяты, дает мне ответ: пункт 3, пункт 2, пункт 1, который неправильный, потому что есть 2 решения: вы берете 1 и 4 или 2 или 3. Как это исправить?

На рисунке ниже таблица с табличным решением по упаковке

Answer 1

Я бы использовал ту же формулу, которую вы используете, чтобы максимизировать значение, чтобы увидеть, какие предметы выбраны, т.е.

if (K[w][i] == K[w-wt[i-1]][i-1] + val[i-1]), затем пункт i выбран, иначе он не выбран, и перейти к предыдущему элементу i-1.

Также может быть более 1 набора элементов, которые при выборе могут дать максимальное значение.

В этом случае ищите каждое такое значение в массиве K[W][..] для максимальногозначение K[W][n] и пройти массив из этой точки, чтобы получить выбранные элементы.

Код:

void knapSack(int W, int wt[], int val[], int n)
{
   int i, w;
   int K[W+1][n+1];
   for (w = 0; w <= W; w++)
   {
    for(i=0;i<=n;i++){
        if(i==0)
            K[w][i]=0;

        if(w<wt[i-1] && i!=0)
            K[w][i]=K[w][i-1];

        if(w>=wt[i-1] && i!=0)
            K[w][i]=max(K[w][i-1],K[w-wt[i-1]][i-1]+val[i-1]);

       }
   }

   cout << "\n" << "Maximum value obtained is : " << K[W][n] << "\n";
   int j;
   for ( j=1; j<=n; j++ ) {
     if (K[W][j] == K[W][n]) {
       int w = W;
       int i = j;
       while(i>0 && w>0){
          if (K[w][i] == K[w-wt[i-1]][i-1] + val[i-1]) {
            cout << "Item " << i << " is in the bag" << "\n";
            w = w - wt[i-1];
            i--;
          } else {
            i--;
          }
        }
      cout<< "\n";
     }
   }

}