算法沉淀——动态规划之完全背包问题
- 01.【模板】完全背包
- 02.零钱兑换
- 03.零钱兑换 II
- 04.完全平方数
完全背包问题是背包问题的一种变体，与01背包问题不同，它允许你对每种物品进行多次选择。具体来说，给定一个固定容量的背包，一组物品，每个物品有重量和价值，目标是找到在背包容量范围内，使得背包中的物品总价值最大的组合。
相较于01背包问题，完全背包问题允许对每个物品进行多次选择，即每个物品都有无限件可用。
动态规划解法：
-
状态转移方程： 考虑第i个物品，可以选择放入背包或者不放入。如果选择放入，那么总价值为dp[i][j-weight[i]] + value[i]，即前i个物品的总价值加上当前物品的价值。如果选择不放入，那么总价值为dp[i-1][j]，即前i-1个物品的总价值。因此，状态转移方程为：
dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i]] + value[i])
其中，dp[i-1][j]表示不放入第i个物品，dp[i][j-weight[i]] + value[i]表示放入第i个物品。
-
初始条件： 当i=0时，表示前0个物品，总价值为0；当j=0时，表示背包容量为0，总价值也为0。
-
遍历顺序： 外层循环遍历物品，内层循环遍历背包容量。
例子：
假设有如下物品：
物品1：重量=2，价值=3 物品2：重量=3，价值=4 物品3：重量=4，价值=5
背包容量为W=8，我们要求解在这个条件下的最大总价值。
按照上述动态规划解法，构建状态转移表如下：
重量/价值 0 1 2 3 4 5 6 7 8 ---------------------------------------------- 物品0 0 0 0 0 0 0 0 0 0 物品1 0 0 3 6 9 12 15 18 21 物品2 0 0 3 6 9 12 15 18 21 物品3 0 0 3 6 9 12 15 18 21
因此，最终结果为dp[3][8] = 21，表示在背包容量为8的情况下，最大总价值为21。这意味着最优解是选择物品1，物品2和物品3各两件放入背包。
01.【模板】完全背包
题目链接：https://www.nowcoder.com/practice/237ae40ea1e84d8980c1d5666d1c53bc?tpId=230&tqId=2032575&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196
你有一个背包，最多能容纳的体积是V。
现在有n种物品，每种物品有任意多个，第i种物品的体积为vi,价值为wi。
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
输入描述：
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个vi和wi表示第i种物品的体积和价值。
1≤n,V≤1000
输出描述：
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。
示例1
输入：
2 6 5 10 3 1
输出：
10 2
示例2
输入：
3 8 3 10 9 1 10 1
输出：
20 0
说明：
无法恰好装满背包。
示例3
输入：
6 13 13 189 17 360 19 870 14 184 6 298 16 242
输出：
596 189
说明：
可以装5号物品2个，达到最大价值298*2=596，若要求恰好装满，只能装1个1号物品，价值为189.
思路
第一问：
- 状态表示：
- dp[i][j] 表示从前 i 个物品中挑选，总体积不超过 j，所有选法中能挑选出的最大价值。
- 状态转移方程：
- 根据最后一步的状况，分情况讨论：
- 选 0 个第 i 个物品：相当于去前 i - 1 个物品中挑选，总体积不超过 j，最大价值为 dp[i - 1][j]。
- 选 1 个第 i 个物品：相当于去前 i - 1 个物品中挑选，总体积不超过 j - v[i]。此时最大价值为 dp[i - 1][j - v[i]] + w[i]。
- 综上，状态转移方程为：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])。
- 初始化：
- 多加一行，将第一行初始化为 0，因为什么也不选时，满足体积不小于 j 的情况，此时价值为 0。
- 填表顺序：
- 从上往下填表。
- 返回值：
- 根据状态表示，返回 dp[n][V]。
- 根据最后一步的状况，分情况讨论：
第二问：
- 状态表示：
- dp[i][j] 表示从前 i 个物品中挑选，总体积正好等于 j，所有选法中能挑选出来的最大价值。
- 状态转移方程：
- dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])。
- 在使用 dp[i][j - v[i]] 时，需要判断 j >= v[i] 且 dp[i][j - v[i]] 表示的状态是否存在，即 dp[i][j - v[i]] != -1。
- 初始化：
- 多加一行，将第一个格子设置为 0，因为正好能凑齐体积为 0 的背包；但是第一行后面的格子都设置为 -1，因为没有物品，无法满足体积大于 0 的情况。
- 填表顺序：
- 从上往下填表。
- 返回值：
- 由于最后可能凑不成体积为 V 的情况，因此返回之前需要特判一下。
空间优化：
对于背包问题，一般都可以使用「滚动数组」来进行空间上的优化，即减少状态表示的维度。
在 01 背包问题中，优化的结果为：
- 删掉所有的横坐标。
- 修改一下 j 的遍历顺序。
这样的优化是因为在计算 dp[i][j] 时，只依赖于上一行 dp[i-1][j] 和 dp[i-1][j-v[i]]，而 dp[i-1][j-v[i]] 在当前行的计算过程中已经被更新过，因此不需要保留整个二维数组。
代码
#include #include #include using namespace std; const int N=1002; int n,V,v[N],w[N]; int dp[N][N]; int main() { cin>>n>>V; for(int i=1;i>v[i]>>w[i]; for(int i=1;i dp[i][j]=dp[i-1][j]; if(j=v[i]) dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]); } cout dp[i][j]=dp[i-1][j]; if(j=v[i]&&dp[i][j-v[i]]!=-1) dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]); } cout const int INF=0x3f3f3f3f; public: int coinChange(vector int n=coins.size(); vector dp[i][j]=dp[i-1][j]; if(j=coins[i-1]) dp[i][j]=min(dp[i][j],dp[i][j-coins[i-1]]+1); } return dp[n][amount]=INF?-1:dp[n][amount]; } }; public: int change(int amount, vector int n=coins.size(); vector dp[i][j]=dp[i-1][j]; if(j=coins[i-1]) dp[i][j]=dp[i][j]+dp[i][j-coins[i-1]]; } return dp[n][amount]; } }; const int INF=0x3f3f3f3f; public: int numSquares(int n) { int m=(int)sqrt(n); vector dp[i][j]=dp[i-1][j]; if(j=i*i) dp[i][j]=min(dp[i][j],dp[i][j-i*i]+1); } return dp[m][n]; } };
