背包问题

背包问题

一个商品如果可以重复多次放入是完全背包，而只能放入一次是01背包

01背包：

问题描述：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

一维dp

1. 确定dp数组以及下标的含义：

p[j] 表示容量为j的背包的价值总和最大是多少

2. 确定递推公式：

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3. 初始化dp数组：

• dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0；
• 如果题目给的价值都是正整数那么非0下标都初始化为0；
• 01背包的dp数组初始化为0;

4. 确定遍历顺序：

• 二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小；
• 倒序遍历是为了保证物品i只被放入一次；
• 先遍历物品再遍历背包容量是保证每个容量可放入多个物品；

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量, j必须>=weight[i];
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

5. 举例推导···

完全背包

问题描述：

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

• 01背包和完全背包唯一不同就是体现在遍历顺序上;

• 01背包中一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量；

• 完全背包物品和背包的先后遍历顺序都可以，区别是求组合还是排列数；

• 01背包内嵌(背包容量)的循环是从大到小遍历，为了保证每个物品仅被添加一次；

• 而完全背包的物品是可以添加多次的，所以完全背包的内嵌遍历顺序要从小到大去遍历；

• 如果求组合数就是外层for循环遍历物品，内层for遍历背包。

• 如果求排列数就是外层for遍历背包，内层for循环遍历物品。

一维dp

// 先遍历物品，再遍历背包
// 组合
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

// 先遍历背包，再遍历物品
// 排列
for (int j = 0; j <= amount; j++) { // 遍历背包容量
    for (int i = 0; i < coins.size(); i++) { // 遍历物品
        if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
    }
}

总结

• 问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

• 问装满背包有几种方法：dp[j] += dp[j - nums[i]]；(初始化dp[0] = 1)

• 问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

• 问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

---

【参考资料】代码随想录、力扣