java多重背包算法,[z]多重背包中多次背包 O(VN)算法1 (单调队列优化)

偏执的太偏执、 2022-11-18 13:43 5阅读 0赞

多次背包

多次背包问题：给定 n 种物品和一个背包。第 i 种物品 的价值是 Wi ，其体积

为 Vi，数量是 Ki件，背包的容量为 C。可以任意选择装入背包中的物品，求装入背

包中物品的最大总价值。

方法一：可以把此物品拆分成Ki个只能用一次的物品，直接套用 0-1 背包问题的经典动规实现，但是效率太低了，需要寻找更高效的算法。此算法时间复杂度为O(C\*∑(Ki))

方法二：拆分成体积和价值分别为原来1, 2 , 4..   2^m,    Ki-2^m 倍的几个物品，用0-1背包求解。 时间复杂度为O(C\*∑(\[log2Ki\]))

方法三(本文重点)：(对单调队列没有了解的请参见原论文\[本文结尾链接\])对于第 i 种物品来说，已知体积 v，价值 w，数量 k，那么可以按照当前枚举的体积 j 对v的余数把整个动规数组分成 v份，以下是 v=3 的情况：

j             0 1 2 3 4 5 6 7 8 ……

j mod v   0 1 2 0 1 2 0 1 2 ……

我们可以把每一份分开处理，假设余数为 d。

编号j         0     1        2            3           4             5         ……

对应体积 d    d+v    d+2\*v     d+3\*v    d+4\*v      d+5\*v    ……

现在看到分组以后，编号 j 可以从 j-k 到 j-1 中的任意一个编号转移而来(因为相邻的体积正好相差 v) ，这看上去已经和区间最大值有点相似了。但是注意到由于体积不一样，显然体积大的价值也会大于等于体积小的，直接比较是没有意义的，所以还需要把价值修正到同一体积的基础上。比如都退化到 d，也就是说用 F\[j\*v+d\]- j\*w来代替原来的价值进入队列。

对于物品i，伪代码如下

1. FOR d: = 0 TO v-1                     //枚举余数，分开处理

2.   清空队列

3.   FOR j: = 0 TO (C-d) div v           //j 枚举标号，对应体积为 j\*v+d

4.    INSERT j , F\[ j\*v+d \] – j \* w      //插入队列

5.    IF A\[ L \] < j - k THEN L + 1 → L //如果队列的首元素已经失效

6.    B\[ L \] + j \* w → F\[ j\*v+d \]       //取队列头更新

7.   END FOR

8. END FOR

已知单调队列的效率是 O(n)，那么加上单调队列优化以后的多次背包，

效率就是 O(n\*C)了。

(详细请参见原论文)

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

完整程序如下(Pascal)：

var

a,b,f:array\[0..100000\] of longint;

m,s,c,n,t,i,j,l,r,d:longint;

procedure insert(x,y:longint);

begin

while (l<=r)and(b\[r\]<=y) do dec(r);

inc(r);a\[r\]:=x;b\[r\]:=y;

end;

begin

readln(n,t);              //读入数据 n为物品个数 t为背包容量

for i:=1 to n do

begin

read(m,s,c);         //读入当前物品 m为物品体积、s为物品价值、c为物品可用次数(0表示无限制)

if (c=0)or(t div m

for d:=0 to m-1 do

begin

l:=1;r:=0;     //清空队列

for j:=0 to (t-d) div m do

begin

insert(j,f\[j\*m+d\]-j\*s);   //将新的点插入队列

if a\[l\]

f\[j\*m+d\]:=b\[l\]+j\*s;        //用队列头的值更新f\[j\*m+d\]

end;

end;

end;

writeln(f\[t\]);

end.

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

本文内容参考国家集训队2009论文 徐持衡《浅谈几类背包题》

发表评论取消回复

表情：

评论列表（有 0 条评论，5人围观）

还没有评论，来说两句吧...

相关阅读

相关多重背包问题

多重背包问题 1、参考资料 https://blog.csdn.net/qq\_38984851/article/details/81133840 https:/

╰半夏微凉°/ 2022年11月27日 07:24/ 0 赞/ 206 阅读

相关 java多重背包算法,[z]多重背包中多次背包 O(VN)算法1 (单调队列优化)

多次背包多次背包问题：给定 n 种物品和一个背包。第 i 种物品的价值是 Wi ，其体积为 Vi，数量是 Ki件，背包的容量为 C。可以任意选择装入背包中的物品，求装

偏执的太偏执、/ 2022年11月18日 13:43/ 0 赞/ 6 阅读

相关背包问题详解：01背包、完全背包、多重背包

参考链接： 1. [http://www.cnblogs.com/fengty90/p/3768845.html][http_www.cnblogs.com_fengty9

蔚落/ 2022年09月30日 00:54/ 0 赞/ 233 阅读

相关背包问题(0-1背包、完全背包、多重背包)详解

背包问题一个背包总容量为V, 现在有N个物品, 第i个物品容量为weight\[i\], 价值为value\[i\], 现在往背包里面装东西, 怎样装才能使背包内物品总

柔情只为你懂/ 2022年06月08日 00:59/ 0 赞/ 337 阅读

相关算法——背包问题 01背包+完全背包+多重背包

01背包：https://biancheng.love/problem/51/index 有n 种不同的物品，每个物品有两个属性，weight重量，value 价值，现在给一

ゞ浴缸里的玫瑰/ 2022年06月06日 10:41/ 0 赞/ 293 阅读

相关多重背包

问题：一个容量为c的背包，还有一些物品（每个物品有具体的数量num），这些物品的体积w和价值v各不相同。求出能在不超过c的情况下尽可能的使价值最大。对于多重背包问题，可

妖狐艹你老母/ 2022年05月31日 01:19/ 0 赞/ 207 阅读

相关背包问题-01背包，完全背包，多重背包

背包问题-01背包，完全背包，多重背包 -------------------- 01背包：概念：有Goods\_Num件物品，MAX\_V

太过爱你忘了你带给我的痛/ 2022年05月14日 09:23/ 0 赞/ 281 阅读

相关多重背包

n个物品，每个可以取k次，容量为w，价值为v。一般做法：二进制拆分：将每个物品拆成O(log k)个01背包的物品，时间复杂度为(nmlogk) 例如：K=10 可以拆分

矫情吗；*/ 2021年12月23日 11:05/ 0 赞/ 326 阅读

相关多重背包问题

转自：[http://www.cnitblog.com/luckydmz/archive/2008/08/06/47719.aspx][http_www.cnitblog.co

青旅半醒/ 2021年12月16日 12:39/ 0 赞/ 292 阅读

相关多重背包二进制优化

多重背包二进制优化将\\(num\\)件，价值\\(v\\)，花费\\(cost\\)的物品\\((v,w)\\)拆分为\\((v,w),(v\\times 2^1,w

迈不过友情╰/ 2021年12月03日 18:39/ 0 赞/ 233 阅读