使用递归算法解决背包

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），并且很难判断哪一个更快。