存档

文章标签 ‘二进制拆分’

多重背包

2012年6月11日 6 条评论

---

前面已经回顾了01背包完全背包,本节回顾多重背包的几种实现形式,主要有以下几方面内容:

==多重背包问题定义 & 基本实现

==多重背包二进制拆分实现

==防火防盗防健忘

========================================

多重背包问题定义 & 基本实现

问题:有个容量为V大小的背包,有很多不同重量weight[i](i=1..n)不同价值value[i](i=1..n)的货物,第i种物品最多有n[i]件可用,计算一下最多能放多少价值的货物。

对于多重背包的基本实现,与完全背包是基本一样的,不同就在于物品的个数上界不再是v/c[i]而是n[i]与v/c[i]中较小的那个。状态转移方程如下


f(i,v) = max{ f(i-1,v-k*c[i]) + k*w[i] | 0<=k<=n[i] }

代码与完全背包的区别仅在内部循环上由


for(k = 1; k <= j/weight[i]; ++k)

变为


for(k = 1; k <=n[i] && k<=j/weight[i]; ++k)

当然,输入上的区别就不说了。

阅读全文...

完全背包

2012年6月11日 5 条评论

---

前面回顾了01背包,在此基础上本节回顾完全背包的几种实现形式,主要有以下几方面内容:

==完全背包问题定义 & 基本实现

==完全背包二进制拆分思想

==完全背包使用滚动数组(略)

==完全背包中的逆向思维

==完全背包使用一维数组

========================================

完全背包问题定义 & 基本实现

问题:有个容量为V大小的背包,有很多不同重量weight[i](i=1..n)不同价值value[i](i=1..n)的货物,每种物品有无限件可用,想计算一下最多能放多少价值的货物。

与01背包不同的是,完全背包每件物体可以放入无限件(只要能放的下),故对于每件物品i,相当于拆分成了v/c[i]件相同的物品,拆分之后物品i就不是放入或不放入的两种情况了,而是放入0件、放入1件、放入2件…等情况了,对于该件物品i,最大价值取放入k件的最大值,故状态转移方程为:


f(i,v) = max{ f(i-1,v-k*c[i]) + k*w[i] | 0<=k<=v/c[i] }

各状态的意义不再赘述,上代码,关于复杂度以及每种物品的状态数见代码注释:

阅读全文...