动态规划-01背包问题

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. 删掉所有的横坐标；

        ii.修改一下j的遍历顺序

#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;
}