当前位置: 首页> 教育> 幼教 > [动态规划]---背包问题

[动态规划]---背包问题

时间:2025/7/11 8:43:23来源:https://blog.csdn.net/qq_61552595/article/details/141675022 浏览次数:0次

前言

作者:小蜗牛向前冲

专栏:小蜗牛算法之路

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

 

一、【模板】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;// 第二问// 重新设置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];}
};

 

 

关键字:[动态规划]---背包问题

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: