C++中的背包問題說明和源碼示例

問題說明

有N件物品和一個容量為V的背包。

第i件物品的重量是w[i]，價值是v[i]。

求解將哪些物品裝入背包可使這些物品的重量總和不超過背包容量，

且價值總和最大。

功能說明

本程序用動態(tài)規(guī)劃的思想解決了背包問題，并用了兩種算法：迭代法、遞歸法。在迭代法中實現(xiàn)了打印背包問題的表格。

代碼簡述

通過用戶輸入數(shù)據(jù)，程序輸入檢測，動態(tài)分配空間，選擇算法， 用動態(tài)規(guī)劃的思想求解背包問題。

迭代法：

通過遍歷n行W列，迭代每行每列的值，并把最優(yōu)解放到 n行（在數(shù)組中為第n+1行）W列（在數(shù)組中為第W+1列）中。

遞歸法：

通過每次返回前i個物品和承重為j的最優(yōu)解， 遞歸計算總背包問題的最優(yōu)解。

源碼示例

#include #include using namespace std;
int **T = NULL;    // 存儲背包問題表格的數(shù)組指針
// 返回兩個值的最大值int max(int a, int b) {  return (a > b) ? a : b;}
// 迭代法，能顯示背包問題的表格int packIterative(int n, int W, int *w, int *v) {    // 循環(huán)遍歷n行  for (int i = 1; i <= n; ++i)  {    // 循環(huán)遍歷W列    for (int j = 1; j <= W; ++j)    {      //第i個物品能裝下，則比較包括第i個物品和不包括第i個物品，取其最大值      if (w[i] <= j)        T[i][j] = max(v[i] + T[i - 1][j - w[i]], T[i - 1][j]);
      // 第i個物品不能裝下，則遞歸裝i-1個      else        T[i][j] = T[i - 1][j];    }  }  return T[n][W];}
// 遞歸法，不支持顯示背包問題的表格int packRecursive(int n, int W, int *w, int *v) {  // 結(jié)束條件（初始條件），i或者j為0時最大總價值為0  if (n == 0 || W == 0) {    return 0;  }  // 第i個物品不能裝下，則遞歸裝i-1個  if (w[n] > W) {    return packRecursive(n - 1, W, w, v);  }  //第i個物品能裝下，則比較包括第i個物品和不包括第i個物品，取其最大值  else {    return max(v[n] + packRecursive(n - 1, W - w[n], w, v), packRecursive(n - 1, W, w, v));  }}
// 打印背包問題的表格void printT(int n, int W){  // 打印n行  for (auto i = 0; i <= n; i++)  {    // 打印行數(shù)    cout << i << ":	";
    // 打印W列    for (int w = 0; w <= W; w++)    {      cout << T[i][w] << "	";    }
    // 換行    cout << endl;  }}
int main() {  int *w = NULL;    // 存儲每件物品重量的數(shù)組指針  int *v = NULL;    // 存儲每件物品價值的數(shù)組指針  int n;        // 物品個數(shù)n  int W;        // 背包總承重W
  cout << "---------------- 背包問題 ----------------" << endl;  cout << "請輸入物品數(shù) n (n>=0) " << endl;
  // 輸入背包數(shù)  cin >> n;
  if (cin.fail() || n < 0)  {    cout << "輸入n錯誤！" << endl;    system("pause");    return 0;  }
  cout << "請輸入背包承重量 W (W>=0) " << endl;
  // 輸入背包承重量  cin >> W;
  if (cin.fail() || W < 0)  {    cout << "輸入W錯誤！" << endl;    system("pause");    return 0;  }
  // 分配空間  // 對w和v分配n+1大小  w = new int[n + 1];  v = new int[n + 1];
  // 對T分配n+1行，并初始化為0  T = new int *[n + 1]();  // 對T分配W+1列，并初始化為0  for (auto i = 0; i <= n; i++)  {    T[i] = new int[W + 1]();  }
  // 輸入背包的重量和價值  for (auto i = 1; i <= n; i++)  {    cout << "請輸入第 " << i << " 個物品的重量和價值（用空格隔開）" << endl;    cin >> w[i] >> v[i];    if (cin.fail() || w[i] < 0 || v[i] < 0)    {      cout << "輸入錯誤！" << endl;      system("pause");      return 0;    }  }
  cout << "------------------------------------------------" << endl;  cout << "請選擇算法：" << endl;  cout << "【1】迭代法" << endl;  cout << "【2】遞歸法" << endl;  cout << "------------------------------------------------" << endl;
  int choose;
  // 輸入算法的選擇  cin >> choose;  switch (choose)  {  case 1:  {    // 迭代法，能顯示背包問題的表格    cout << "能裝下物品的最大價值為 " << packIterative(n, W, w, v) << endl;    cout << "------------------------------------------------" << endl;    printT(n, W);    break;  }  case 2:  {    // 遞歸法，不支持顯示背包問題的表格    cout << "能裝下物品的最大價值為 " << packRecursive(n, W, w, v) << endl;    break;  }  default:  {    cout << "輸入錯誤！" << endl;    break;  }  }
  cout << "------------------------------------------------" << endl;
  delete w;  delete v;  for (int i = 0; i <= n; ++i) {    delete[] T[i];  }  delete[] T;
  system("pause");  return 0;}

今天的分享就到這里了，大家要好好學(xué)C++喲~