[动态规划]---背包问题
前言
作者：小蜗牛向前冲
一、【模板】0/1背包
1、题目描述
描述
你有一个背包，最多能容纳的体积是V。
现在有n个物品，第i个物品的体积为v;,价值为wi。
(1)求这个背包至多能装多大价值的物品?
(2)若背包恰好装满，求至多能装多大价值的物品?
输入描述:
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数u;和u;，表示第i个物品的体积和价值。
1≤n, V,vi, wi< 1000
输出描述:
第一行输出第一问的答案，
输出有两行，(
第二行输出第二问的答案，如果无
解请输出0。
示例1
输入：
3 5 2 10 4 5 1 4复制输出：
14 9复制说明：
装第一个和第三个物品时总价值最大，但是装第二个和第三个物品可以使得背包恰好装满且总价值最大。示例2
输入：
3 8 12 6 11 8 6 8复制输出：
8 0复制说明：
装第三个物品时总价值最大但是不满，装满背包无解。备注：
要求O(nV)的时间复杂度，O(V)空间复杂度
对于背包问题的解决方法 就是动态规划的思路：
2、状态表示
根据经验+题目要求：我们以前想的最多的是,dp[i]表示，从前i个物品中选，所有选法中，挑出礼物最大的价值。但是这里发现不行，因为这里还体积的限制。
对于0/1背包是有二种问法的，选出最大价值，不超过体积或者正好等于体积容量。
- dp[i][j]，表示从前i个物品中选择，总体积不超过j,所有选法中，能挑选出来的最大礼物的价值。
- dp[i][j]，表示从前i个物品中选择，总体积正好等于j,所有选法中，能挑选出来的最大礼物的价值。
3、状态转移方程
根据最后一步进行情况讨论：
- 选第不i个物品：dp[i-1][j]
- 选择第i个物品:w[i]+dp[i-1][j-v[i]](这里的w表示价值，v表示体积)
从而推出状态方程：
dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]）
4、初始化
这里我们选择的一个二维dp，为dp多增加一行，初始化为0即可。
5、填表顺序
由于状态转移方程可以知道从上往下填表就可以了。
6、返回值
dp[n][v]
7、解题代码
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int main() {
int n, V;
cin >> n >> V;
vector<int> w(n + 1), v(n + 1);
// 这里为了下面填表方便，从1位置开始填写
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
// 背包问题
// 创建dp表
vector<vector<int>> dp(n + 1, vector<int>(V + 1));
// 第一问
// 填表
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= V; j++) {
// i位置不选择
dp[i][j] = dp[i - 1][j];
if (j - v[i] >= 0) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
}
}
}
cout << dp[n][V] << endl;
// 第二问
// 重新设置dp
dp.clear();
dp.resize(n + 1, vector<int>(V + 1, 0));
// 初始化, dp[0][0] 应该是0，因为没有物品的时候重量为0
dp[0][0] = 0;
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++) { // 注意这里从0开始
// i位置不选择
dp[i][j] = dp[i - 1][j];
if (j - v[i] >= 0 && 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;
}
这里我们还可以通过滚动数组的方式，将二维dp，优化为一维的dp
其实非常简单，就将所有的横坐标删除，填表我们从右往左进行填表
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int main() {
int n, V;
cin >> n >> V;
vector<int> w(n + 1), v(n + 1);
// 这里为了下面填表方便，从1位置开始填写
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
// 背包问题
// 创建dp表
vector<int> dp(V + 1);
// 第一问
// 填表
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;
// 第二问
// 重新设置dp
dp.clear();
dp.resize(V + 1, 0);
// 初始化
dp[0] = 0;
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;
}
这里温馨提醒一下：不要强行去解释 滚动后的数组的状态表示和状态方程，这里没有必要（何必涂增烦恼）。
二、0/1背包刷题
话不多说，勤学多练
1、分割等和子集
这里的关键是我们要进行转换，这里我们要求分割后 等和子集，我们这里就可以转换为，数组和为sum,也就是说如果我们能够选择出一个sum/2来，就可以分割为一个等和子集
你们在这里就可以想到，就是从数组中挑选数组，凑成sum/2,数组中的每个数都是可以选择或者不选，这个不就0/1背包问题吗？我们就可以顺着这个思路去写动态规划。
class Solution {
public:
bool canPartition(vector<int>& nums)
{
//这里我们要转换为0/1背包问题
//在数组中选择一些数和等于sum/2
int n = nums.size();
int sum = 0;
for(int i = 0;i<n;i++)
{
sum +=nums[i];
}
if(sum%2)//不能均分为二部分，肯定不能分割
{
return false;
}
//状态表示：dp[i][j]:在前i位置挑选，在所有选发中能够凑成j这个数(true,false)
vector<vector<bool>> dp(n+1,vector<bool>(sum/2+1));
//初始化
for(int i = 0;i<=n;i++)
{
dp[i][0] = true;
}
//填表
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=sum/2;j++)
{
//i位置不选
dp[i][j] = dp[i-1][j];
if(j>=nums[i-1])//这里要注意下标的映射
{
dp[i][j] = dp[i][j]||dp[i-1][j-nums[i-1]];
}
}
}
//返回
return dp[n][sum/2];
}
};空间优化：
class Solution {
public:
bool canPartition(vector<int>& nums)
{
//这里我们要转换为0/1背包问题
//在数组中选择一些数和等于sum/2
int n = nums.size();
int sum = 0;
for(int i = 0;i<n;i++)
{
sum +=nums[i];
}
if(sum%2)//不能均分为二部分，肯定不能分割
{
return false;
}
//状态表示：dp[i][j]:在前i位置挑选，在所有选发中能够凑成j这个数(true,false)
vector<bool> dp(sum/2+1);
//初始化
dp[0] = true;
//填表
for(int i = 1;i<=n;i++)
{
for(int j = sum/2;j>=nums[i-1];j--)
{
dp[j] = dp[j]||dp[j-nums[i-1]];
}
}
//返回
return dp[sum/2];
}
};