01背包问题
由于leetcode上没原题,故参考卡哥意见自己编题记录一下。
背包大重量为4。物品为:
物品名称 | 重量 | 价值 |
---|---|---|
0 | 1 | 15 |
1 | 3 | 20 |
2 | 4 | 30 |
– | – | – |
问背包能背的物品大价值是多少?
二、解法二维dp:
递推公式:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
void test_2_wei_bag_problem1() {vectorweight = {1, 3, 4};
vectorvalue = {15, 20, 30};
int bagweight = 4;
// 二维数组
vector>dp(weight.size(), vector(bagweight + 1, 0));
// 初始化
for (int j = weight[0]; j<= bagweight; j++) {dp[0][j] = value[0];
}
// weight数组的大小 就是物品个数
for(int i = 1; i< weight.size(); i++) {// 遍历物品
for(int j = 0; j<= bagweight; j++) {// 遍历背包容量
if (j< weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
cout<< dp[weight.size() - 1][bagweight]<< endl;
}
int main() {test_2_wei_bag_problem1();
}
一维dp:
递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
void test_1_wei_bag_problem() {vectorweight = {1, 3, 4};
vectorvalue = {15, 20, 30};
int bagWeight = 4;
// 初始化
vectordp(bagWeight + 1, 0);
for(int i = 0; i< weight.size(); i++) {// 遍历物品
for(int j = bagWeight; j >= weight[i]; j--) {// 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout<< dp[bagWeight]<< endl;
}
int main() {test_1_wei_bag_problem();
}
三、问答题为什么二维dp两个for循环的嵌套顺序这么写?反过来写行不行?
答:反过来可以,原因是递推公式里本层遍历输入都在本层的左上角。
讲一讲初始化的逻辑。
答:二维背包中,dp[i][0],无论是选取哪些物品,背包价值总和一定为0;而dp[0][i], 当 i >= weight[0] 时 = value[0],否则为0; 其他无所谓,都会被覆盖。
一维背包中,dp[0] = 0, 如果如果题目给的价值都是正整数那么非0下标都初始化为0就可以了,如果题目给的价值有负数,那么非0下标就要初始化为负无穷。这样才能让dp数组在递归公式的过程中取的大的价值,而不是被初始值覆盖了。
一维数组的01背包,两个for循环的顺序反过来写行不行?为什么?
答:不可以。因为一维dp的写法,背包容量一定是要倒序遍历(倒序遍历是为了保证物品i只被放入一次!),如果遍历背包容量放在上一层,那么每个dp[j]就只会放入一个物品,即:背包里只放入了一个物品。(原因是,dp数组初始化是0,在先遍历背包容量时,由于从后向前遍历,dp[j - weight[i]] = 0, 没用上上一个状态。)
倒序遍历的原因是,本质上还是一个对二维数组的遍历,并且右下角的值依赖上一层左上角的值,因此需要保证左边的值仍然是上一层的,从右向左覆盖。
Leetcode 416. 分割等和子集你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
文章标题:代码随想录算法训练营第42天|01背包问题416.分割等和子集-创新互联
本文URL:https://www.cdcxhl.com/article36/epdsg.html
成都网站建设公司_创新互联,为您提供企业网站制作、虚拟主机、网站维护、App开发、关键词优化、企业建站
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联