-
UID：5472
-
- 注册时间2007-08-19
- 最后登录2010-11-20
- 在线时间6小时
-
- 发帖71
- 搜Ta的帖子
- 精华0
- OI财富800
- 威望126
- 贡献值0
- 交易币0
-
访问TA的空间加好友用道具
|
例如01背包问题，开[1..10000,1..10000]肯定mle 怎么办呢？ 由于动态规划只需要用前n个数值，那么[1..10000,0..n]就够了 - 具体实现如下
- 假设是01背包问题，需要用前1个数组的值，那么就[1..10000,0..1]
- 开一个变量（例如c）
- 每次循环就
- for i:=1 to 10000 do begin
- c:=1-c
- f[i,c]:=max{f[i,1-c],f[i-w[i],,1-c}
- 从而实现节约空间
- c为最后的状态
附01背包问题滚动数组解： - 光光的作业（homework）
- [问题描述]
- 光光上了高中，科目增多了。在长假里，光光的老师们都非常严厉，都给他布置了一定量的作业。假期里，光光一共有的时间是k 小时。在长假前，老师们一共给光光布置了n 份作业，第i 份作业需要的时间是ti 小时。但是由于老师们互相不商量，因此光光有可能不能完成老师的作业。当可能不能完成老师的作业时，光光就事后去向老师说明，然后被老师批评一顿了事。
- 对于一件作业，只有2 种情况：完成或者不完成（快要完成也算不完成）。如果没完成，受到批评是天经地义的。但是，不同的作业对于光光来说，批评的力度是不同的。第i 件作业如果没完成，就要受到pi 个单位的批评。
- 多次这样之后，光光想要在长假前就知道他至少会受到多少个单位的批评。你能帮助他吗？
- [输入]
- 输入文件homework.in 包含以下内容：第一行只有一个数字k。第二行只有一个数字n。接下来n 行，每行两个数字，分别是ti 和pi， 两个数字之间用一个空格分开。
- 100%的数据中，k<=100000，ti<=10000，pi<=10000；
- 30%的数据中，n<=20；
- 100%的数据中，n<=500。
- [输出]
- 输出文件homework.out 仅包含一行，是一个数字，代表了光光最少受到的批评。
- [样例]
- homework.in
- 5
- 3
- 2 6
- 1 3
- 4 7
- homework.out
- 6
- var
- f:array [0..1,0..100000] of longint;
- t,p:array [1..500] of integer;
- k,n,i,j,c,c2,pall:longint;
- begin
- //assign(input,'homework.in'); reset(input);
- //assign(output,'homework.out'); rewrte(output);
- readln(k);
- readln(n);
- pall:=0;
- fillchar(f,sizeof(f),0);
- for i:=1 to n do begin
- readln(t[i],p[i]);
- pall:=pall+p[i];
- for j:=t[i] to k do
- if f[0,j]<p[i] then f[0,j]:=p[i];
- end;
- c:=0;
- for i:=1 to n do begin
- c:=1-c;
- for j:=1 to k do begin
- f[c,j]:=f[c,j-1];
- if j-t[i]>0 then
- if f[1-c,j-t[i]]+p[i]>f[c,j] then f[c,j]:=f[1-c,j-t[i]]+p[i];
- end;
- end;
- writeln(pall-f[c,k]);
- //close(input); close(output);
- end.
楼下的建议已经改了 [ 此贴被liuichou在2007-10-04 12:13重新编辑 ]
|
