[动态规划]---背包问题 - 北京网站建设

前言

作者：小蜗牛向前冲

专栏：小蜗牛算法之路

专栏介绍："蜗牛之道，攀登大厂高峰，让我们携手学习算法。在这个专栏中，将涵盖动态规划、贪心算法、回溯等高阶技巧，不定期为你奉上基础数据结构的精彩算法之旅。一同努力，追逐技术的星辰大海。"

一、【模板】0/1背包

1、题目描述

描述
你有一个背包，最多能容纳的体积是V。
现在有n个物品，第i个物品的体积为v;,价值为wi。
(1)求这个背包至多能装多大价值的物品?
(2)若背包恰好装满，求至多能装多大价值的物品?
输入描述:
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数u;和u;，表示第i个物品的体积和价值。
1≤n, V,vi, wi< 1000
输出描述:
第一行输出第一问的答案，
输出有两行，(
第二行输出第二问的答案，如果无
解请输出0。
示例1

输入：

复制输出：

14
9

复制说明：

装第一个和第三个物品时总价值最大，但是装第二个和第三个物品可以使得背包恰好装满且总价值最大。

示例2

输入：

复制输出：

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;// 第二问// 重新设置dpdp.clear();dp.resize(n + 1, vector<int>(V + 1, 0));// 初始化, dp[0][0] 应该是0，因为没有物品的时候重量为0dp[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;// 第二问// 重新设置dpdp.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/2int 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/2int 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];}
};