问题描述

问题描述

给定一组已知重量和价值的物品和一个容量已知的背包，求解在不超过背包容量情况下，选用那些物品放入背包，使得所选用的所有物品价值最大化。

物品总数N 4
背包容量M 8
每个物品重量wi {5, 4, 3, 2}
每个物品价值vi {15, 10, 6, 2}

问题的判定性说法

image.png

问题的形式化定义

image.png

问题思路

动态规划思路

动态规划解决该问题，类似于莱文斯坦距离的解法类似。利用CAAIS数据来说明这个问题的解决思想。
image.png
动态规划DP方程构造
image.png
PS：V[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值

（整张表格是从上往下，从左往右地填）
举例说明表格中的数值填法，倒数第二行倒数第四列的16 4的填法：

  • 首先不满足DP方程的第一种和第二种情况
  • 所以代入取最大值max函数
    • V（i-1，j）：不选本物品（3，6），还是用之前的值，继承上面的第一个物品和第二个物品，DP值为15 U
    • V（i-1，j）+vi：用该容量（7）-所选物品的重量为4，然后再查容量为4的时候DP值为10，然后求出该情况DP是，10加上该物品的价值，所以该情况下的DP值为16，右上标为4（CAAIS），值来源于前面容量为4的情况。


格子如上方式填就好了！

递归思路

第二节课将递归的时候，也讲了这个问题的递归思路。不过复杂度记得是指数级的，暂时不写了~~

代码实现

动态规划Code

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. namespace NS_DP0_1Knapsack {
  5. int DP0_1Knapsack(int n, int W, int *w, int *v);
  6. void Output(int n, int W, int *w, int *v, int OptV);
  7. static vector<vector<int>> V;
  8. static vector<int> x;
  9. void DP0_1KnapsackCaller(int n, int W, int *w, int *v)
  10. {
  11.     V.clear();
  12.     V.resize(n + 1, vector<int>(W + 1, 0));
  13.     x.resize(n + 1);
  14.     int OptV = DP0_1Knapsack(n, W, w, v);
  15.     Output(n, W, w, v, OptV);
  16. }
  17. int DP0_1Knapsack(int n, int W, int *w, int *v)
  18. {
  19.     for (int i = 1; i <= n; i++)
  20.         for (int j = 1; j <= W; j++)
  21.             if (j < w[i - 1])
  22.                 V[i][j] = V[i - 1][j];
  23.             else if (V[i - 1][j] >=
  24.                 V[i - 1][j - w[i - 1]] + v[i - 1])
  25.                 V[i][j] = V[i - 1][j];
  26.             else
  27.                 V[i][j] = V[i - 1][j - w[i - 1]] + v[i - 1];
  28.     int j = W;
  29.     for (int i = n; i > 0; i--)
  30.         if (V[i][j] == V[i - 1][j])
  31.             x[i] = 0;
  32.         else
  33.         {   x[i] = 1; j -= w[i - 1];  }
  34.     return V[n][W];
  35. }
  36. void Output(int n, int W, int *w, int *v, int OptV)
  37. {
  38.     //inputs
  39.     printf("DP to solve 0-1 knapsack:\n");
  40.     printf("%d items with knapsack capacity %d.\n", n , W);
  41.     printf("%-6s: ", "Weight");
  42.     for (int i = 0; i < n; i++)
  43.         printf("%3d", w[i]);
  44.     printf("\n");
  45.     printf("%-6s: ", "Value");
  46.     for (int i = 0; i < n; i++)
  47.         printf("%3d", v[i]);
  48.     printf("\n");
  49.     //the value matrix
  50.     printf("\nThe value matrix:\n");
  51.     printf("  ");
  52.     for (int j = 0; j <= W; j++)
  53.         printf("%3d", j);
  54.     printf("\n");
  55.     for (int i = 0; i <= n; i++)
  56.     {
  57.         printf("%2d", i);
  58.         for (int j = 0; j <= W; j++)
  59.             printf("%3d", V[i][j]);
  60.         printf("\n");
  61.     }
  62.     //solution
  63.     printf("\nThe optimal value: %d\n", OptV);
  64.     printf("The optimal solution:\n");
  65.     for (int i = 1; i <= n; i++)
  66.         printf("%2d", x[i]);
  67.     printf("\n\n");
  68. }
  69. } //namespace NS_DP0_1Knapsack
  70. using namespace NS_DP0_1Knapsack;
  71. int main()
  72. {
  73.     // 物品个数
  74.     vector<int> N = { 4,  10};
  75.     // 背包容量
  76.     vector<int> W = { 8,  100};
  77.     // 各物品重量
  78.     vector<vector<int>> w = {
  79.         { 5, 4, 3, 2 },
  80.         { 4, 3, 7, 2, 9, 3, 1, 7, 2, 5 }
  81.     };
  82.     // 各物品价值
  83.     vector<vector<int>> v = {
  84.         { 15, 10, 6, 2 },
  85.         { 15, 10, 6, 2, 23, 12, 33, 7, 22, 10 }
  86.     };
  88.     int m = N.size();
  89.     for (int i = 0; i < m; i++)
  90.     {
  91.         DP0_1KnapsackCaller(N[i], W[i], &w[i][0], &v[i][0]);
  92.     }
  94.     return 0;
  95. }

动态规划Result

image.png
image.png
image.png