使用遞歸算法解決揹包

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），並且很難判斷哪一個更快。