做淘宝客新增网站推广,西安建站免费模板,wordpress如何更改上传文件大小,大足网站建设题目#xff1a;01背包理论基础、416. 分割等和子集
参考链接#xff1a;代码随想录
动态规划#xff1a;01背包理论基础
思路#xff1a;01背包是所有背包问题的基础#xff0c;第一次看到比较懵#xff0c;完全不知道dp数据怎么设置。具体分析还是dp五部曲#xff…题目01背包理论基础、416. 分割等和子集
参考链接代码随想录
动态规划01背包理论基础
思路01背包是所有背包问题的基础第一次看到比较懵完全不知道dp数据怎么设置。具体分析还是dp五部曲首先是dp数据先想本题需要求的内容即给定背包容量下求能放置物品的最大价值和因此想到的数据存放内容肯定是最大价值和但本题有容量和物品两个维度而之前的题目都只有一个维度故需要用到二维数据dp[i][j]表示从下标0-i物品中选择任意物品放入容量为j的背包中能得到的最大价值和 然后第二步递推公式要递推考虑第i个物品有两种情况首先是不放i物品这时候dp[i][j]dp[i-1][j]与前i-1个物品的结果相同然后是放i物品这时候背包还剩下的重量为j-weight[i]然后在这些重量中放置前i-1个物品dp[i][j]dp[i-1][j-weight[i]]value[i]最终递推即在这两个里取最大值如果物品i本来就放不进去那么就只有第一种情况第三部dp初始化首先是j0的时候背包放不了任何东西故dp[i][0]0然后是i0即只有物品0的时候这时候就是看背包能不能放下weight[0]如果放得下则为weight[0]否则为0其他都被初始化为0第四步为确定遍历顺序先遍历物品和背包都可以因为都是左上推右下我们就先遍历物品举例略。时间复杂度O(mn)。
#includeiostream
#includecstring
using namespace std;int maxValue(int n,int m,int space[],int value[]){int dp[m][n1];//空间需要0-n,物品从0-m-1即可memset(dp,0,sizeof(dp));for(int i1;in;i){//初始化物品0if(space[0]i){//物品0可以放进背包了dp[0][i]value[0];}}for(int i1;im;i){for(int j1;jn;j){if(space[i]j){//物品i无法先放进去dp[i][j]dp[i-1][j];}else{//先放物品idp[i][j]max(dp[i-1][j],dp[i-1][j-space[i]]value[i]);}}}return dp[m-1][n];
}int main(){int n,m;while(cin m n){int space[m],value[m];for(int i0;im;i){cin space[i];}for(int i0;im;i){cin value[i];}cout maxValue(n,m,space,value) endl;}return 0;
}我比较喜欢的ACM写法是把解题过程抽象成一个函数数据输入全部在main中完成标答是在solve()中处理输入。
看标答发现可以把数据压缩成一维因为递推公式的i都是i-1我们可以只保留每一行也就是滚动数组。新的一维dp数组dp[j]表示容量为j的背包能装入的最大价值递归公式还是看物品i能不能先放进去如果不能那么dp[j]就不变如果能放先放进去那么就比较当前dp[j]和dp[j-weight[i]]value[i]取最大值初始化只初始化一行dp[0]肯定为0其他下标位置也初始化为0因为后面递推过程中会逐渐取最大值遍历顺序这是一维写法比较困难的地方必须从背包容量从大到小遍历因为如果从小到大会把前面的背包放入两次比如w[0]1,v[0]15在计算dp[1]的过程中即为dp[0]v[0]15而对dp[2]如果取dp[1]value[0]30会算两次物品0而从大到小遍历我们一开始没有放入物品dp[0]初始化均为0dp[2]dp[1]value[0]15因为在这一次遍历中还没有考虑到dp[1]后续计算dp[1]dp[0]value[0]15故不会重复放入而之前的二维数组每一次dp[i][j]都由上一层计算而来本层的没有被覆盖过因此不存在重复计算问题举例略。主要就是为了避免本层覆盖的问题因为dp数组都是由上一层计算的。一维滚动数组写法的代码如下
int maxValue(int n,int m,int space[],int value[]){int dp[n1]{0};for(int i1;in;i){//初始化if(space[0]i){//物品0可以放进背包了dp[i]value[0];}}for(int i1;im;i){for(int jn;j0;j--){if(space[i]j){//物品i能先放进去dp[j]max(dp[j],dp[j-space[i]]value[i]);}}}return dp[n];
}真正理解需要画图分析。一维写法空间复杂度大幅下降需要掌握。
416. 分割等和子集
思路本题的第一想法就是使用回溯暴力搜索和为sum/2的所有元素如果找到返回true。能不能套用01背包问题呢把数组中所有元素对应为物品每个物品只能放入一次背包的容量为sum/2放入的物品重量为元素的数值价值也为元素的数值需要保证背包正好装满。对应dp五部曲首先是dp数组dp[j]表示背包容量为j时能放入最大价值若背包容量为target则dp[target]即背包装满后的容量dp[target]target即装满如果装不满即价值未达到要求dp[target]target递推公式物品i能放进去的时候dp[j]max(dp[j],dp[j-nums[i]]nums[i])因为物品i的weight和value都是nums[i]初始化由于题目的价值都是非负dp直接全初始化为0即可递推顺序按重量从大到小举例略。时间复杂度O(nm),m为和。
class Solution {
public:bool canPartition(vectorint nums) {int sumaccumulate(nums.begin(),nums.end(),0);//库函数求和if(sum%21){//和为奇数直接排除return false;}int targetsum/2;vectorint dp(20001,0);//由题意知最大的和不会超过20000int nnums.size();for(int i0;in;i){for(int jtarget;jnums[i];j--){dp[j]max(dp[j],dp[j-nums[i]]nums[i]);}}if(dp[target]target){//容量为target的背包装完后价值恰好为target即表示装满return true;}return false;}
};本题的难点就在于将原问题和01背包对应起来主要是装满如何想到即把价值和重量都定义成元素的值装满target重量即为target容量的背包能装的最大价值恰好为target即dp[target]target。
