设有ｎ种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为ＸＫ，今从ｎ种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于ＸＫ，而价值的和为最大。输入数据：第一行两个数：物品总数Ｎ，背包载重量ＸＫ；两个数用空格分隔；第二行N个数,为Ｎ种物品重量；两个数用空格分隔；第三行N个数,为N种物品价值; 两个数用空格分隔；输出数据：第一行总价值；以下N行，每行两个数，分别为选取物品的编号及数量；输入样例：4 102 3 4 71 3 5 9 输出样例：122 14 1 求源程序~~~

明显的无限背包
var
     v,t:array[1..10000] of longint;
     f,s,p:array[0..10000] of longint;
     x:array[0..10000,0..10000] of longint;
     i,j,k,m,n:longint;
begin
     assign(input,'tiancai.in');reset(input);
     assign(output,'tiancai.out');rewrite(output);
     readln(m,n);
     for i:=1 to m do
       read(t[i]);readln;
     for i:=1 to m do
       read(v[i]);
     fillchar(f,sizeof(f),0);
     fillchar(s,sizeof(s),0);
     fillchar(x,sizeof(x),0);
     for i:=1 to m do
       for j:=t[i] to n do
         if f[j]<f[j-t[i]]+v[i] then
         begin
           f[j]:=f[j-t[i]]+v[i];
           s[j]:=s[j-t[i]]+1;
           for k:=1 to s[j-t[i]] do
           x[j,k]:=x[j-t[i],k];
           x[j,s[j]]:=i;
         end;
     writeln(f[n]);
     fillchar(p,sizeof(p),0);
     for i:=1 to s[n] do
     inc(p[x[n,i]]);
     for i:=1 to m do
     if p[i]<>0 then writeln(i,'   ',p[i]);
     close(input);close(output);
end.
额   没有优化 具体的自己剪枝


我的好像fillchar太多了 会超时 你自己改一下

能不能帮忙解读一下背包问题。用递归算法。

能不能详细点儿