再帰アルゴリズムを使ってナップザックを解く

Question

私はこのアルゴリズムをテキストブックから実装しようとしています。

私はこれを書いた：ここ

// Knapsack_memoryfunc.cpp : Defines the entry point for the console application. 
//Solving Knapsack problem using dynamic programmig and Memory function 

#include "stdafx.h" 
#include "iostream" 
#include "iomanip" 
using namespace std; 

int table[20][20] = { 0 }; 
int value, n, wt[20], val[20], max_wt; 

// ---CONCERNED FUNCTION----- 

int MNSack(int i, int j) 
{ 
    value = 0; 
    if (table[i][j] < 0) 
     if (j < wt[i]) 
      value = MNSack(i - 1, j); 
     else 
      value = fmax(MNSack(i - 1, j), val[i] + MNSack(i - 1, j - wt[i])); 

    table[i][j] = value; 
    return table[i][j]; 
} 

// -------------------------- 

void items_picked(int n, int max_wt) 
{ 
    cout << "\n Items picked : " << endl; 
    while (n > 0) 
    { 
     if (table[n][max_wt] == table[n - 1][max_wt]) // if value doesnot change in table column-wise, item isn't selected 
      n--;          // n-- goes to next item 
     else           // if it changes, it is selected 
     { 
      cout << " Item " << n << endl; 
      max_wt -= wt[n];       // removing weight from total available (max_wt) 
      n--;          // next item 
     } 
    } 
} 

int main() 
{ 

    cout << " Enter the number of items : "; 
    cin >> n; 
    cout << " Enter the Maximum weight : "; 
    cin >> max_wt; 
    cout << endl; 
    for (int i = 1; i <= n; i++) 
    { 
     cout << " Enter weight and value of item " << i << " : "; 
     cin >> wt[i] >> val[i]; 
    } 

    for (int i = 0; i <= n; i++) 
     for (int j = 0; j <= max_wt; j++) 
      table[i][j] = 0; 

    for (int i = 1; i <= n; i++) 
     for (int j = 1; j <= max_wt; j++) 
      table[i][j] = -1; 

    cout << " Optimum value : " << MNSack(n, max_wt); 

    cout << " \n Table : \n"; 
    for (int i = 0; i <= n; i++) 
    { 
     for (int j = 0; j <= max_wt; j++) 
      if (table[i][j] == -1) 
       cout << setw(5) << "-"; 
      else 
       cout << setw(5) << table[i][j]; 
     cout << endl; 
    } 

    items_picked(n, max_wt); 


    return 0; 
} 

は、質問と出力されます：

それは最適値のようないくつかの場所でその正しいように思える、まだないです十分に受け入れられる。 私はそれをデバッグしようとしましたが、再帰的な関数では非常に難しいです。誰かが助けてくれますか？

Answer 1

int MNSack(int i, int j) 
{ 
    value = 0; 
    if (table[i][j] < 0) 
    { 
     if (j < wt[i]) 
      value = MNSack(i - 1, j); 
     else 
      value = max(MNSack(i - 1, j), val[i] + MNSack(i - 1, j - wt[i])); 

     table[i][j] = value; 
    } 
    return table[i][j]; 
} 

ここに問題があります。テーブルアイテムが0より大きい場合、再帰はスキップされますが、テーブルアイテムが0より大きい場合でもテーブルアイテムは0より大きくなります。

テーブル項目を変更する必要があるときは、中括弧に入れてこれを修正します。

Answer 2

ボトムアップ溶液。

#include <iostream> 
#include <algorithm> 
#include <iomanip> 
using namespace std; 


int main() 
{ 
    int table[20][20] = { 0 }; 
    int value, n, wt[20], val[20], max_wt; 

    cout << " Enter the number of items : "; 
    cin >> n; 
    cout << " Enter the Maximum weight : "; 
    cin >> max_wt; 
    cout << endl; 
    for (int i = 1; i <= n; i++) 
    { 
     cout << " Enter weight and value of item " << i << " : "; 
     cin >> wt[i] >> val[i]; 
    } 

    // Initialization 
    for (int i = 0; i <= n; i++) 
     for (int j = 0; j <= max_wt; j++) 
      table[i][j] = 0; 

    // In practice, this can be skipped in a bottom up solution 
    for (int i = 1; i <= n; i++) 
     for (int j = 1; j <= max_wt; j++) 
      table[i][j] = -1; 

    for (int i = 1; i <= n; i++) 
    { 
     for (int j = 1; j <= max_wt; j++) 
     { 
      if (j < wt[i]) 
       table[i][j] = table[i - 1][j]; 
      else 
       table[i][j] = max(table[i - 1][j], val[i] + table[i - 1][j - wt[i]]); 
     } 
    } 

    cout << " Optimum value : " << table[n][max_wt] << endl; 

    cout << " \n Table : \n"; 
    for (int i = 0; i <= n; i++) 
    { 
     for (int j = 0; j <= max_wt; j++) 
      if (table[i][j] == -1) 
       cout << setw(5) << "-"; 
      else 
       cout << setw(5) << table[i][j]; 
     cout << endl; 
    } 

    return 0; 
} 

これは再帰をループに変更し、グローバル変数を避けることがわかります。また、コードが簡単になるため、テーブル項目が有効かどうかをチェックすることもできます（例では-1）。

このソリューションの欠点は、常にすべての可能なノードを横断することです。しかし、再帰とテーブル項目の二重チェックがより多くのコストを要するため、項目ごとにより良い係数が得られます。トップダウンとボトムアップはどちらも同じオーダーの複雑さO（n^2）を持ち、どれが速いのかを判断するのは難しいです。