算法沉淀——动态规划之完全背包问题（leetcode真题剖析）

算法沉淀——动态规划之完全背包问题

01.【模板】完全背包02.零钱兑换03.零钱兑换 II04.完全平方数

完全背包问题是背包问题的一种变体，与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

输出：

示例2

输入：

3 8

3 10

9 1

10 1

输出：

说明：

无法恰好装满背包。

示例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

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<

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])<

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 <= 121 <= coins[i] <= 231 - 10 <= 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& coins, int amount) {

int n=coins.size();

vector> dp(n+1,vector(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 <= 3001 <= coins[i] <= 5000coins 中的所有值互不相同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& coins) {

int n=coins.size();

vector> dp(n+1,vector(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> dp(m+1,vector(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];

}

};

夸智网

算法沉淀——动态规划之完全背包问题（leetcode真题剖析）

算法 [动态规划]---part1

算法沉淀——动态规划之子序列问题（下）（leetcode真题剖析）

发表评论取消回复

夸智网

算法沉淀——动态规划之完全背包问题（leetcode真题剖析）

算法 [动态规划]---part1

算法沉淀——动态规划之子序列问题（下）（leetcode真题剖析）

相关文章

发表评论取消回复