程序地带

两种01背包


无法更简单的dp问题



文章目录
符号约定
每个物品
 
1
 
~1~
 1 个每个物品
 

 
~infty~
 ∞ 个每个物品
 
n
u
m
b
e
r
[
k
]
 
~number[k]~
 number[k] 个总结


符号约定


k
   
k~~~
k   只取前k个/前k种物品
C
   
C~~~
C   背包容量


每个物品
 
1
 
~1~
 1 个
// 没考虑 basis 情形 (即: dp中哪些元素是0)
dp[k][C] = {
if (weight[k] > C) {
dp[k-1][C];
// 不可能带走物品k, 因为太重, 拿不动
}
else {
max{
dp[k-1][C],
// 拿走物品k导致总体收益下降, 所以不拿走物品k
dp[k-1][C-weight[k]] + value[k];
// 拿走物品k不导致总体收益下降, 所以拿走物品k
};
}
}
每个物品
 

 
~infty~
 ∞ 个
// 没考虑 basis 情形 (即: dp中哪些元素是0)
dp[C] = {
max(for all k from 1 upto n){
if (weight[k] <= C) {
dp[C-weight[k]] + value[k];
}
}
}
每个物品
 
n
u
m
b
e
r
[
k
]
 
~number[k]~
 number[k] 个
// 没考虑 basis 情形 (即: dp中哪些元素是0)
dp[k][C] = {
if (weight[k] > C) {
dp[k-1][C];
// 不可能带走物品k, 因为太重, 拿不动
}
else {
max(for all x from 1 upto number[k]){
dp[k-1][C],
// 拿走物品k导致总体收益下降, 所以不拿走物品k
dp[k-1][C-weight[k]*x] + value[k]*x
// 拿走物品k不导致总体收益下降, 所以拿走物品k
};
}
}
总结

如果已知dp的正确性, 就能给出相应的dp算法; 如果已知dp算法, 就能给出相应的dp的正确性.


dp的正确性 与 dp算法 的关系类似对偶问题.


接下来从dp的正确性的角度分析以上算法.


dp的正确性 等价于 问题的最优子结构.


所以只需要说明问题的最优子结构.


思想
每次不完全解答问题, 只解答问题的一部分甚至: 每次都不验证一个解是否满足条件, 只验证解的一部分是否满足条件 关键
严格 缩小问题规模

01背包的子结构有两个维度, 都是 最优子结构


物品种类k背包称重C

更一般的, "每个物品
 

 
~infty~
 ∞ 个"的情形我们可以写成如下形式, 和我们之前所写的形式易见是等价的


// 没考虑 basis 情形 (即: dp中哪些元素是0)
dp[k][C] = {
if (weight[k] > C) {
dp[k-1][C];
}
else {
max{
dp[k-1][C],
// 拿走物品k导致总体收益下降, 所以不拿走物品k
dp[k][C-weight[k]] + value[k]
// 拿走物品k不导致总体收益下降, 所以拿走物品k
};
}
}

其他dp问题


问题dp算法All-Pairs-Shortest-Path(APSP)Floyd算法, 类似每个物品
 
1
 
~1~
 1 个的01背包问题

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/int_main_Roland/article/details/112689272

随机推荐

如何在 Apple Silicon (M1) 上开发 Teams App

apple在几个月前发布了自家的芯片M1,由于将多核cpu,多核gpu,神经网络运算,内存和其他一切处理部件高度整合在一起,大大提...

Tony.X 阅读(139)

rdlc报表 矩形高固定_财务分析3(财务报表分析指南)

财务报表分析指南选择优质股票是财务分析的主要目的。所谓优质股票是指公司的获利能力强、发展势头好或具有潜在的爆发力。投资者购买这样的优质股票,在牛市中涨幅大,而在熊市中抗跌性好。它不仅具有投资的价值,而...

weixin_39641257 阅读(105)

27丨案例:带宽消耗以及Swap(上)

 今天我们来看一个真实的案例。事情是这样的,之前有人在微信上问我一个问题,这个问题的现象很典型:典型的TPS上不去,响应时间增加,...

ths512 阅读(706)

时间工具类

packagecom.pistonint.idata.common.util;importorg.joda.time.DateTime;importorg.joda.time.Duration;imp...

八点二十四分 阅读(447)

2021-01-04

C++中vector的使用方法1.基本信息在c++中,vector是一个十分有用的容器。作用:它能够像容器一样存放各种类型的对象࿰...

weixin_45693482 阅读(384)

Example实现and =1(a=1 or b=1)

配置搜索条件ZhyExamplezhyExample=newZhyExample();ZhyExample.Criteriacriteria=zhyExample.createCrit...

会迟到但不会缺席 阅读(158)