• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

单调队列优化多重背包(pascal及翻译过去的C代码)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

  我最开始接触的相对高级的DP算法是从背包问题开始的。那是上学期新生赛的事,当时,在第二轮选拔赛中,有一道可能算是贪心算法的题,但是在我眼里却觉得这是一道背包问题。于是,我求助我们学校的大牛,问一下有什么关于背包算法的,而且比较容易让我弄懂的资料,最终他介绍我看《背包九讲》。

  那时,甚至到现在,我只会基础的0-1背包,完全背包,多重背包的O(NClogC)算法……

  一直卡着我的是多重背包的O(NC)算法。这个是我从一一篇叫做《国家集训队2008论文集——浅谈几类背包问题》的文章中看到的。我到现在都无法理解单调队列优化多重背包的原理,但是在网上找到一些关于单调队列优化多重背包的代码。对我来说,要理解一种算法的原理最好的方法是模拟算法的运行,因为我的快排原理和0-1背包的原理都是这样弄懂的。在网上只找到pascal的代码,而我把他翻译成C语言的,并且测试是正确的:

View Code
 1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #include<math.h>
5
6 #define Infp 0x7fffffff
7 #define Infn 0x80000000
8 #define DisCon 1000000000
9 #define MAX 999999999
10 #define MIN -999999999
11
12 #define Zero(a) memset(a, 0, sizeof(a))
13 #define Copy(a, b) memcpy(a, b, sizeof(b))
14 #define Pi acos(-1)
15 #define FMAX (1E300)
16 #define FMIN (-1E300)
17 #define feq(a, b) (fabs((a)-(b))<1E-6)
18 #define flq(a, b) ((a)<(b)||feq(a, b))
19 #define RG 1005
20
21 /**
22 var
23 a,b,f:array[0..100000] of longint;
24 m,s,c,n,t,i,j,l,r,d:longint;
25 /**/
26
27 __int64 a[100005], b[100005], f[100005];
28 __int64 m, s, c, n, t, l, r;
29
30 /**
31 procedure insert(x,y:longint);
32 begin
33 while (l<=r)and(b[r]<=y) do dec(r);
34 inc(r);a[r]:=x;b[r]:=y;
35 end;
36 /**/
37
38 void insert(__int64 x, __int64 y)
39 {
40 while(l<=r&&b[r]<=y)
41 r--;
42 r++;
43 a[r]=x;
44 b[r]=y;
45 }
46 /**
47 begin
48 readln(n,t); //读入数据 n为物品个数 t为背包容量
49 for i:=1 to n do
50 begin
51 read(m,s,c); //读入当前物品 m为物品体积、s为物品价值、c为物品可用次数(0表示无限制)
52 if (c=0)or(t div m<c) then c:=t div m;
53 for d:=0 to m-1 do
54 begin
55 l:=1;r:=0; //清空队列
56 for j:=0 to (t-d) div m do
57 begin
58 insert(j,f[j*m+d]-j*s); //将新的点插入队列
59 if a[l]<j-c then inc(l); //删除失效点
60 f[j*m+d]:=b[l]+j*s; //用队列头的值更新f[j*m+d]
61 end;
62 end;
63 end;
64 writeln(f[t]);
65 end.
66 /**/
67 int main()
68 {
69 scanf("%I64d%I64d", &n, &t);
70 Zero(a);
71 Zero(b);
72 Zero(f);
73
74 for(__int64 i=1; i<=n; i++)
75 {
76 scanf("%I64d%I64d%I64d", &m, &s, &c);
77 if(c==0||t/m<c)c=t/m;
78 for(__int64 d=0; d<=m-1; d++)
79 {
80 l=1;
81 r=0;
82 for(__int64 j=0; j<=(t-d)/m; j++)
83 {
84 insert(j, f[j*m+d]-j*s);
85 if(a[l]<j-c)
86 l++;
87 f[j*m+d]=b[l]+j*s;
88 }
89 }
90 }
91 printf("%I64d\n", f[t]);
92
93 return 0;
94 }

  

  我先把它分享到这里,虽然我目前仍未弄懂,所以只好等我以后明白了,再补充我的见解!

  好的我现在去模拟运行,希望能尽快弄明白~

 

 

View Code
 1     for(__int64 i=1; i<=n; i++)
2 {
3 scanf("%I64d%I64d%I64d", &m, &s, &c);
4 if(c==0||t/m<c)c=t/m;
5 for(__int64 d=0; d<=m-1; d++)
6 {
7 l=1;
8 r=0;
9 for(__int64 j=0; j<=(t-d)/m; j++)
10 {
11 insert(j, f[j*m+d]-j*s);
12 if(a[l]<j-c)
13 l++;
14 f[j*m+d]=b[l]+j*s;
15 }
16 }
17 }
18 printf("%I64d\n", f[t]);

  补充1:如果用上面的代码,这个不就成了背包的万能公式了吗?

  生搬硬套应该也可以解决不少背包的基本问题吧?


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
c#Liststring的用法发布时间:2022-07-13
下一篇:
I2C总线信号时序总结【转】发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap