http://www.rqnoj.cn/RankList.asp?Page=5（第五页）
[color=red]NOIp2010将至 希望能取得好成绩！[/color]
[color=blue]附题解：
背包九讲 的经典问题
背包为零时的处理上一直没有很好思路
开始是直接赋值为价值WA70
后来想到了初始化为-maxlongint f[0][1]=0 的思路——AC
初看过背包九讲的可能不明白何谓“合并有序队列”实际上就是对数组进行排序（降序）为了节省时间采取的类似队列的方式：
∵原来两数组是有序的
∴每次取两队列头较大的个加入新数组 新的数组一定是有序的
[/color]
题目:多人背包
状态: [color=green]Accepted[/color]
测评机： Xeost[5]
得分： 100分
提交日期： 2010-10-28 7:06:00
有效耗时： 4078毫秒
测试结果1: [color=green]通过本测试点|有效耗时157ms [/color]
测试结果2: [color=green]通过本测试点|有效耗时171ms [/color]
测试结果3: [color=green]通过本测试点|有效耗时204ms [/color]
测试结果4: [color=green]通过本测试点|有效耗时296ms [/color]
测试结果5: [color=green]通过本测试点|有效耗时469ms [/color]
测试结果6: [color=green]通过本测试点|有效耗时563ms [/color]
测试结果7: [color=green]通过本测试点|有效耗时656ms [/color]
测试结果8: [color=green]通过本测试点|有效耗时750ms [/color]
测试结果9: [color=green]通过本测试点|有效耗时766ms [/color]
测试结果10: [color=green]通过本测试点|有效耗时46ms [/color]
提交代码：
const maxv=5000;maxn=200;
type q=array[0..100]of longint;
var f:array[0..maxv]of q;
w,v:longint;
d:q;
max,ans:longint;
i,j,k,m,n,vv:longint;
function work(a,b:q;ww:longint):q;
var c:q;
ss,ii,jj,kk,ah,bh:longint;
begin
fillchar(c,sizeof(c),0);
if w<>0 then for ii:=1 to k do inc(b[ii],w);
ah:=1;bh:=1;
for ii:=1 to k do
begin
if a[ah]>=b[bh] then
begin
c[ii]:=a[ah];
inc(ah);
end
else
begin
c[ii]:=b[bh];
inc(bh);
end;
end;
exit(c);
end;
{main}
begin
readln(k,vv,n);
for i:=1 to k do
for j:=0 to vv do
f[j][i]:=-maxlongint;
f[0][1]:=0;
for n:=1 to n do
begin
readln(v,w);
for i:=vv downto v do
if f[i-v][1]>=0 then f[i]:=work(f[i],f[i-v],w);
end;
for i:=1 to k do inc(ans,f[vv][i]);
writeln(ans);
end.
[color=pink]
P.S.在此感谢我的老师们 计算机老师（提供机房）、历史、地理、政治、校本、研究性学习、美术、音乐、体育、通用技术老师（翘了他们很多节课 挺对不起他们的= =！）[/color]