郑州手机网站制作公司,赣州微网站建设费用,wap网站制作,网络营销工具的定义01 背包 题目描述#xff1a;有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]#xff0c;得到的价值是value[i] 。每件物品只能用一次#xff0c;求解将哪些物品装入背包里物品价值总和最大。 二维dp数组01背包#xff1a;
确定dp数组以及下标的含义 … 01 背包 题目描述有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。 二维dp数组01背包
确定dp数组以及下标的含义 对于背包问题有一种写法 是使用二维数组即dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。 确定递推公式 再回顾一下dp[i][j]的含义从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。那么可以有两个方向推出来dp[i][j] 不放物品i由dp[i - 1][j]推出即背包容量为j里面不放物品i的最大价值此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时物品i无法放进背包中所以背包内的价值依然和前面相同。)放物品i由dp[i - 1][j - weight[i]]推出dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值那么dp[i - 1][j - weight[i]] value[i] 物品i的价值就是背包放物品i得到的最大价值 所以递归公式 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); 初始化 dp[i][j]是由其左侧和左上方数据推导出来的因此要初始化dp[i][0]列和dp[0][j]行的数据背包重量为0时背包内物品的价值为零dp[i][0]列为0。dp[0][i]行的数据当背包容量j≥wieght[j]时dp[0][j]value[j]其他时候为零。 遍历顺序 先遍历还是weight还是value都可以。
#includeiostream
#includevector
using namespace std;void slove(int m, int n){vectorint wight;vectorint value;int x;for (int i 0; i m;i){cinx;wight.push_back(x);}for (int i 0; i m;i){cinx;value.push_back(x);}vectorvectorint dp(m,vectorint(n1,0));for(int j 0; j n; j){if(jwight[0]){dp[0][j] value[0];}}for (int i 1; i m; i){for (int j 1; j n; j){if(j wight[i]){dp[i][j] dp[i-1][j];} else {dp[i][j] max(dp[i-1][j], dp[i-1][j-wight[i]]value[i]);}}}cout dp[m-1][n] endl;
}int main(){int m,n;cinmn;slove(m,n);
}一维dp数组01背包
对于背包问题其实状态都是可以压缩的。
在使用二维数组的时候递推公式dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上表达式完全可以是dp[i][j] max(dp[i][j], dp[i][j - weight[i]] value[i]);
与其把dp[i - 1]这一层拷贝到dp[i]上不如只用一个一维数组了只用dp[j]一维数组也可以理解是一个滚动数组。
但是这里要注意dp数组的遍历要为倒序遍历倒序遍历是为了保证物品i只被放入一次。但如果一旦正序遍历了那么物品0就会被重复加入多次
#includeiostream
#includevector
using namespace std;void slove(int m, int n){vectorint wight;vectorint value;int x;for (int i 0; i m;i){cinx;wight.push_back(x);}for (int i 0; i m;i){cinx;value.push_back(x);}vectorint dp(n1,0);for (int i 0; i m; i){for (int j n; j 0; j--){if(j wight[i]){dp[j] max(dp[j], dp[j-wight[i]]value[i]);}}}cout dp[n] endl;
}int main(){int m,n;cinmn;slove(m,n);
}416. 分割等和子集 题目链接分割等和子集 题目描述给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 解题思想
要明确本题中我们要使用的是01背包因为元素我们只能用一次。
回归主题首先本题要求集合里能否出现总和为 sum / 2 的子集。
那么来一一对应一下本题看看背包问题如何来解决。
只有确定了如下四点才能把01背包问题套到本题上来。
背包的体积为sum / 2背包要放入的商品集合里的元素重量为 元素的数值价值也为元素的数值背包如果正好装满说明找到了总和为 sum / 2 的子集。背包中每一个元素是不可重复放入。
后面的解题思路就和01背包问题相同
class Solution {
public:bool canPartition(vectorint nums) {int sum 0;int target 0;for (int num : nums)sum num;if (sum % 2)return false;elsetarget sum / 2;vectorint dp(target 1, 0);for (int i 0; i nums.size(); i) {for (int j target; j nums[i]; j--) {dp[j] max(dp[j], dp[j - nums[i]] nums[i]);}}if (dp[target] target) {return true;}return false;}
};
