题干

今天有一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？

思路

艹，典型动态规划(状态变化，每次变化择最优)，所以，要思考：

• 状态是啥？
• 选择是啥？
• 状态转移方程是啥？

1. 寻找状态和选择

状态是要变化的量，有两个：背包当前容量和当前可选择的物品数。 选择是每次状态转移时，择优在哪些选择里择：在两个里择，分别是装入包和不装包。

今天我们可以套框架了, 以下是我们之前提过的动态规划框架的伪代码：

for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 择优(选择1，选择2...)

2. 明确dp数组，并细化框架

具体到问题，我们可以定义dp数组的含义。一般dp数组存的就是你要解出的量，为价值，所以，今天我们dp[i][w]的含义是:在当前可选的i个物品下，背包当前容量为w的状态下，包包中能装下的价值。

我们还要找个基类情况，比如当i=0，即没有物品可选时，dp为0，或者w=0，即当包没有余下容量时，dp为0

所以，添加基类，并具体化框架，伪代码结果为：

int[][] dp[N+1][W+1]
dp[0][...] = 0;
dp[...][0] = 0;
for i in [1 .. N]:
  for w in [1 .. W]:
    dp[i][w] = max (装物品i，不装物品i);

return dp[N][W]

3.明确状态转移的选择逻辑，进一步细化框架

即用状态转移方程描述max (装物品i，不装物品i)。

对于dp[i][w],wt[i]代表物品i重，val[i]代表物品i价值： 今天，我选择把物品i装包： dp[i][w] = dp[i-1][w-wt[i-1]] + val[i-1] 之所以用i-1表示第i个物品，因为i从1开始,所以索引i-1用到wt，val数组里时，代表了第i个物品的重量和价值.

今天，我选择不装包： dp[i][w] = dp[i-1][w] 之所以i-1，可选物品减少，是说明排除了一个物品的选择。

可以写出状态转移方程，细化伪代码：

int[][] dp[N+1][W+1]
dp[0][...] = 0;
dp[...][0] = 0;
for i in [1 .. N]:
  for w in [1 .. W]:
    dp[i][w] = max (dp[i-1][w],
                    dp[i-1][w - wt[i-1]] + val[i-1]
               );

return dp[N][W]

4. 伪代码的实际代码实现

注意： w - wt[i-1] 可能小于 0 导致数组索引越界,需要小心边界条件。物理意义是装下去直接爆背包重量，所以选择不放入。

int pack(int W, int N, vector<int>& wt, vector<int>& val) {
    
    // base case 初始化
    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= N; i++) {
        for (int w = 1; w <= W; w++) {
            if (w - wt[i-1] < 0) {
                // 这种情况下只能选择不装入背包
                dp[i][w] = dp[i - 1][w];
            } else {
                // 装入或者不装入背包，择优
                dp[i][w] = max(dp[i - 1][w - wt[i-1]] + val[i-1], 
                               dp[i - 1][w]);
            }
        }
    }
    
    return dp[N][W];
}

Copyright

思路基于fucking-algorithm.