有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。
分析
多重背包问题和完全背包问题形式上是差不多的,就是在物品的数量上限定了范围,所以我们第一点就能想到的是枚举物品的数量,这就是朴素做法
代码
1 | #include <iostream> |
优化
三重循环在较小的数据下是可以通过的,但是当数据稍微大一点的时候,三重循环就很容易超时。我们就可以想办法减少一重循环,第一二重循环是不能被减少的,所以只能从第三层循环入手。
第三层循环的作用是遍历物品的个数,我们想到可以实现把s件物品进行重组可以视作得到一个新的物品,这样就可以在第一重循环中实现遍历他的作用。
因为我们需要做决策就是说这个物品选还是不选,联想到二进制位上是1还是0,所以我们有能力用极小的组合去表示所有情况
代码
1 | #include <iostream> |
本文作者: jiangyuhao
本文链接: http://example.com/2022/04/10/%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!