![cover](https://img-blog.csdnimg.cn/direct/daa6a8deb51c4ab0a576674944a74875.jpeg)
算法沉淀——动态规划之完全背包问题(leetcode真题剖析)
完全背包问题是背包问题的一种变体,与01背包问题不同,它允许你对每种物品进行多次选择。具体来说,给定一个固定容量的背包,一组物品,每个物品有重量和价值,目标是找到在背包容量范围内,使得背包中的物品总价值最大的组合。
算法沉淀——动态规划之完全背包问题
完全背包问题是背包问题的一种变体,与01背包问题不同,它允许你对每种物品进行多次选择。具体来说,给定一个固定容量的背包,一组物品,每个物品有重量和价值,目标是找到在背包容量范围内,使得背包中的物品总价值最大的组合。
相较于01背包问题,完全背包问题允许对每个物品进行多次选择,即每个物品都有无限件可用。
动态规划解法:
-
定义状态: 通常使用二维数组
dp[i][j]
表示在前i
个物品中,背包容量为j
时的最大总价值。 -
状态转移方程: 考虑第
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。 -
遍历顺序: 外层循环遍历物品,内层循环遍历背包容量。
-
返回结果: 最终结果存储在
dp[N][W]
中,其中N
为物品数量,W
为背包容量。
例子:
假设有如下物品:
物品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 <iostream>
#include <algorithm>
#include <cstring>
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<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=0;j<=V;j++)
{
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[n][V]<<endl;
memset(dp,0,sizeof dp);
for(int j=1;j<=V;j++) dp[0][j]=-1;
for(int i=1;i<=n;i++)
for(int j=0;j<=V;j++)
{
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<<(dp[n][V]==-1?0:dp[n][V])<<endl;
return 0;
}
02.零钱兑换
题目链接:https://leetcode.cn/problems/coin-change/
给你一个整数数组 coins
,表示不同面额的硬币;以及一个整数 amount
,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1
。
你可以认为每种硬币的数量是无限的。
示例 1:
输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1
示例 2:
输入:coins = [2], amount = 3
输出:-1
示例 3:
输入:coins = [1], amount = 0
输出:0
提示:
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
思路
- 状态表示:
dp[i][j]
表示从前i
个硬币中挑选,总和正好等于j
,所有选法中最少的硬币个数。
- 状态转移方程:
- 在完全背包问题中,每个硬币可以选无限个,因此需要分多种情况讨论:
- 选
0
个第i
个硬币:相当于去前i - 1
个硬币中挑选,总和正好等于j
。此时最少的硬币个数为dp[i - 1][j]
。 - 选
1
个第i
个硬币:相当于去前i - 1
个硬币中挑选,总和正好等于j - coins[i]
。因为挑选了一个第i
个硬币,此时最少的硬币个数为dp[i][j - coins[i]] + 1
。
- 选
- 综上,状态转移方程为:
dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i]] + 1)
。
- 在完全背包问题中,每个硬币可以选无限个,因此需要分多种情况讨论:
- 初始化:
- 初始化第一行,将第一个位置设置为
0
,因为正好能凑齐总和为0
的硬币;其余位置设置为无穷大。
- 初始化第一行,将第一个位置设置为
- 填表顺序:
- 从上往下填表。
- 返回值:
- 根据状态表示,返回
dp[n][V]
。但要特判一下,因为有可能凑不到。
- 根据状态表示,返回
代码
class Solution {
const int INF=0x3f3f3f3f;
public:
int coinChange(vector<int>& coins, int amount) {
int n=coins.size();
vector<vector<int>> dp(n+1,vector<int>(amount+1));
for(int j=1;j<=amount;j++) dp[0][j]=INF;
for(int i=1;i<=n;i++)
for(int j=0;j<=amount;j++)
{
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];
}
};
03.零钱兑换 II
题目链接:https://leetcode.cn/problems/coin-change-ii/
给你一个整数数组 coins
表示不同面额的硬币,另给一个整数 amount
表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0
。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1:
输入:amount = 5, coins = [1, 2, 5]
输出:4
解释:有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:
输入:amount = 3, coins = [2]
输出:0
解释:只用面额 2 的硬币不能凑成总金额 3 。
示例 3:
输入:amount = 10, coins = [10]
输出:1
提示:
1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins
中的所有值 互不相同0 <= amount <= 5000
思路
- 状态表示:
dp[i][j]
表示从前i
个硬币中挑选,总和正好等于j
,一共有多少种选法。
- 状态转移方程:
- 在完全背包问题中,每个硬币可以选无限个,因此需要分多种情况讨论:
- 选
0
个第i
个硬币:相当于去前i - 1
个硬币中挑选,总和正好等于j
。此时的选法数为dp[i - 1][j]
。 - 选
1
个第i
个硬币:相当于去前i - 1
个硬币中挑选,总和正好等于j - coins[i]
。因为挑选了一个第i
个硬币,此时的选法数为dp[i][j - coins[i]] + 1
。
- 选
- 综上,状态转移方程为:
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]] + 1
。
- 在完全背包问题中,每个硬币可以选无限个,因此需要分多种情况讨论:
- 初始化:
- 初始化第一行,表示没有物品,总和正好为
0
的情况。只有一种情况,即dp[0][0] = 1
;其余位置都为0
种情况。
- 初始化第一行,表示没有物品,总和正好为
- 填表顺序:
- 从上往下填表。
- 返回值:
- 根据状态表示,返回
dp[n][V]
。
- 根据状态表示,返回
代码
class Solution {
public:
int change(int amount, vector<int>& coins) {
int n=coins.size();
vector<vector<int>> dp(n+1,vector<int>(amount+1));
dp[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=amount;j++){
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];
}
};
04.完全平方数
题目链接:https://leetcode.cn/problems/perfect-squares/
给你一个整数 n
,返回 和为 n
的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1
、4
、9
和 16
都是完全平方数,而 3
和 11
不是。
示例 1:
输入:n = 12
输出:3
解释:12 = 4 + 4 + 4
示例 2:
输入:n = 13
输出:2
解释:13 = 4 + 9
提示:
1 <= n <= 104
思路
-
状态表示:
- 在这个问题中,状态表示我们需要找到使得和为
n
的最少完全平方数的数量。因此,我们可以定义状态dp[i][j]
,其中i
表示使用前i
个完全平方数,j
表示目标和为j
。dp[i][j]
的值表示使用前i
个完全平方数达到和为j
时的最小数量。
- 在这个问题中,状态表示我们需要找到使得和为
-
状态转移方程:
-
根据问题的特点,我们可以得到状态转移方程:
dp[i][j]=min(dp[i][j],dp[i][j-i*i]+1);
其中,
i*i
表示第i
个完全平方数。
-
-
初始化:
- 在初始化阶段,我们需要初始化第一行和第一列的值。对于第一行,因为使用零个完全平方数就能达到和为
0
,所以dp[0][0] = 0
。对于其余的dp[0][j]
,由于没有完全平方数可用,我们设为一个较大的值(代表不可能达到这个和)。对于第一列,因为使用任何完全平方数都可以达到和为0
,所以dp[i][0] = 0
。
- 在初始化阶段,我们需要初始化第一行和第一列的值。对于第一行,因为使用零个完全平方数就能达到和为
-
填表顺序:
- 遍历顺序通常是根据状态转移方程中的依赖关系来确定的。在这里,我们可以先遍历使用的完全平方数
i
,然后遍历目标和j
。
- 遍历顺序通常是根据状态转移方程中的依赖关系来确定的。在这里,我们可以先遍历使用的完全平方数
-
返回值:
- 返回结果是在最后一行
dp[m][n]
中,其中m
表示完全平方数的个数,n
表示目标和。
- 返回结果是在最后一行
代码
class Solution {
const int INF=0x3f3f3f3f;
public:
int numSquares(int n) {
int m=(int)sqrt(n);
vector<vector<int>> dp(m+1,vector<int>(n+1));
for(int j=1;j<=n;j++) dp[0][j]=INF;
for(int i=1;i<=m;i++)
for(int j=0;j<=n;j++){
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];
}
};
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)