1、题目描述(截图来的)
2、题目解析 + 算法原理(第一问)
算法思路: 背包问题的状态表⽰⾮常经典,如果⼤家不知道怎么来的,就把它当成⼀个「模板」记住吧~ 我们先解决第⼀问:
1. 状态表⽰: dp[i][j] 表⽰:从前 i 个物品中挑选,总体积「不超过」 j ,所有的选法中,能挑选出来 的最⼤价值。
2. 状态转移⽅程: 线性 dp 状态转移⽅程分析⽅式,⼀般都是根据「最后⼀步」的状况,来分情况讨论: i. 不选第 i 个物品:相当于就是去前 i - 1 个物品中挑选,并且总体积不超过 j 。此 时 dp[i][j] = dp[i - 1][j] ; ii. 选择第 i 个物品:那么我就只能去前 i - 1 个物品中,挑选总体积不超过 j - v[i] 的物品。此时 dp[i][j] = dp[i - 1][j - v[i]] + w[i] 。但是这种状态不⼀ 定存在,因此需要特判⼀下。 综上,状态转移⽅程为: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]) 。
3、初始化
我们多加⼀⾏,⽅便我们的初始化,此时仅需将第⼀⾏初始化为 0 即可。因为什么也不选,也能 满⾜体积不⼩于 j 的情况,此时的价值为 0 。
4.填表顺序
根据「状态转移⽅程」,我们仅需「从上往下」填表。
5.dp的返回值
返回 dp[n][V]
3、算法思路 + 解析(第二问)
第⼆问仅需微调⼀下 dp 过程的五步即可。 因为有可能凑不⻬ j 体积的物品,因此我们把不合法的状态设置为 -1 。
1. 状态表⽰: dp[i][j] 表⽰:从前 i 个物品中挑选,总体积「正好」等于 j ,所有的选法中,能挑选出 来的最⼤价值。
2. 状态转移⽅程: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]) 。 但是在使⽤ dp[i - 1][j - v[i]] 的时候,不仅要判断 j >= v[i] ,⼜要判断 dp[i - 1][j - v[i]] 表⽰的情况是否存在,也就是 dp[i - 1][j - v[i]] != -1 。
3. 初始化: 我们多加⼀⾏,⽅便我们的初始化: i. 第⼀个格⼦为 0 ,因为正好能凑⻬体积为 0 的背包; ii. 但是第⼀⾏后⾯的格⼦都是 -1 ,因为没有物品,⽆法满⾜体积⼤于 0 的情况。
4. 填表顺序: 根据「状态转移⽅程」,我们仅需「从上往下」填表即可。
5. 返回值: 由于最后可能凑不成体积为 V 的情况,因此返回之前需要「特判」⼀下。
//第一种方案
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
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 - 1][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 - 1][j - v[i]] != -1)
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
}
cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
return 0;
}
4.背包问题的空间优化
空间优化: 背包问题基本上都是利⽤「滚动数组」来做空间上的优化:
i. 利⽤「滚动数组」优化;
ii. 直接在「原始代码」上修改。
在01背包问题中,优化的结果为:
i. 删掉所有的横坐标;文章来源:https://www.toymoban.com/news/detail-848181.html
ii.修改一下j的遍历顺序文章来源地址https://www.toymoban.com/news/detail-848181.html
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[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 = V; j >= v[i]; j--) // 修改遍历顺序
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
cout << dp[V] << endl;
// 解决第⼆问
memset(dp, 0, sizeof dp);
for(int j = 1; j <= V; j++) dp[j] = -1;
for(int i = 1; i <= n; i++)
for(int j = V; j >= v[i]; j--)
if(dp[j - v[i]] != -1)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
return 0;
}
到了这里,关于动态规划-01背包问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!