动态规划之背包问题

现有n个物品，背包总容量为c，每个物品只有1件数，背包最多能装入价值为多少的物品？

举例：

物品编号 1，2，3，4

物品体积 2，3，4，5

物品价值 3，4，5，6

最大价值为10,即选取2号物品和4号物品

int w[] = { 2,3,4,5 };
int v[] = { 3,4,5,6 };
int backpack(int n, int c, int w[], int v[]) {
  vector<vector<int>> dp(n+1, vector<int>(c+1, 0));
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= c; j++) {
      if (j - w[i] >= 0) {
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
      }
      else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  } 
  return dp[n][c];
}

一、确定状态

变化量有选择物品、背包容量。

如果可以选择第k种物品

对于第k种物品有选择和不选择两种状态，可以有k-1种物品最佳选择决定。

二、转移方程

如果能装下v[j]

装不下，可以理解为第k个物品不影响结果，最大收益为k-1个物品的最大收益。

三、初始条件和边界

初始条件0容量，最大价值全为0；0物品，最大价值全为0；边界i<=n，j<=c

四、如何遍历

一行一行遍历，最终结果返回F[n][c]，n个物品，c容量最大收益。

完全背包问题

题目改成物品不限量

和01背包问题唯一不同的是j是从1到M。01背包问题是在前一个子问题（i-1种物品）的基础上来解决当前问题（i种物品），向i-1种物品时的背包添加第i种物品；而完全背包问题是在解决当前问题（i种物品），向i种物品时的背包添加第i种物品。

转移方程改成

dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);