pascal题目

Question

DD 和好朋友们要去爬山啦！他们一共有 K 个人，每个人都会背一个包。这些包的容量是相同的，都是 V。可以装进背包里的一共有 N 种物品，每种物品都有给定的体积和价值。

在 DD 看来，合理的背包安排方案是这样的：

每个人背包里装的物品的总体积恰等于包的容量。
每个包里的每种物品最多只有一件，但两个不同的包中可以存在相同的物品。
任意两个人，他们包里的物品清单不能完全相同。
在满足以上要求的前提下，所有包里的所有物品的总价值最大是多少呢？

输入格式 Input Format
第一行有三个整数：K、V、N。

第二行开始的 N 行，每行有两个整数，分别代表这件物品的体积和价值。

输出格式 Output Format
只需输出一个整数，即在满足以上要求的前提下所有物品的总价值的最大值。

样例输入 Sample Input
2 10 5
3 12
7 20
2 4
5 6
1 1

样例输出 Sample Output
57

时间限制 Time Limitation
样例说明
一种可以得到最优解的方案是：第一个人背体积为 7、2、1 的三种物品，价值为 25。第二个人背体积为 3、7 的两种物品，价值为 32。总价值 57。

数据范围
总人数 K<=50。

每个背包的容量 V<=5000。

物品种类数 N<=200。

其它正整数都不超过 5000。

输入数据保证存在满足要求的方案。

注释 Hint
样例说明
当桌上有 8 个石子时，先取的 DD 只需要取走 7 个石子剩下 1 个就可以在一步之后保证胜利，输出 1。

当桌上有 9 个石子时。若 DD 取走 2 个，MM 会取走 7 个，剩下 0 个，DD 输。若 DD 取走 3 个，MM 会取走 5 个，剩下 1 个，DD 输。DD 取走 5 个或者 7 个的情况同理可知。所以当桌上有 9 个石子时，不管 DD 怎么取，MM 都可以让 DD 输，输出 -1。

当桌上有 16 个石子时，DD 可以保证在 3 步以内取得胜利。可以证明，为了在 3 步内取得胜利，DD 第一步必须取 7 个石子。剩下 9 个石子之后，不管第二步 MM 怎么取，DD 取了第三步以后可以保证胜利，所以输出 3。

数据范围
输入文件中的数据数 N<=10。

每次桌上初始的石子数都不超过 20000。

Flag Unaccepted
题号 P1100
类型(?) 动态规划
通过 1人
提交 111次
通过率 1%
难度 4

提交 讨论 题解

Answer 1

program

const
maxv=5000;//最大背包体积
maxn=200;//最大背包数量
maxk=50;//最大人数
var
v,w:array[1..maxn]of longint;//存放i件物品的体积和价值
f:array[0..maxv,0..maxk] of longint;//动态规划数组,f[i,j]表示容量为i的背包的j优解
t:array[0..maxk]of longint;//辅助数组
get,noget,i,j,k,n,vv,temp,num,h,m,c,k1,k2,total:longint;

begin
readln(k,vv,n);//读入人数,背包的容量,物品数量
for i:= 1 to n do
readln(v[i],w[i]);//读入i件物品的体积和价值
for i:= 0 to vv do
begin
for j:= 1 to k do
f[i,j]:=-maxlongint;//初始化数组,因为为完全背包,所以初始化成-maxlongint
f[i,0]:=0; //f[i,0]表示容量为i的背包能有多少个解,上限是k
end;
f[0,0]:=1; f[0,1]:=0;
for i:= 1 to n do
begin
for j:= vv - v[i] downto 0 do
begin
//将f[j+v[i],h]备份到t数组里，因为求f[j+v[i]][1..k]时会覆盖掉原来的数据
for h:= 1 to f[j+v[i],0] do
t[h]:=f[j+v[i],h];

k1:=f[j,0]; k2:=f[j+v[i],0];
c:=k1+k2; //计算背包容量为j+v[i]时能产生的解个数
if c>k then c:=k;//如果解超过k个,那么只需求出前k个
f[j+v[i],0]:=c; //保存背包容量为j+v[i]时能产生的解个数
get:=1;noget:=1;//设置指针,get指向f[j],表示取物品i时,f[j+v[i],h]是由f[j]的第get优解+w[i]得到的; noget指向辅助数组t, 表示不取物品i时,f[j+v[i],h]是由t的第noget优解得到的,及原来的f[j+v[i],get]. 思想相当于双递增队列。
for h:= 1 to c do
begin
if ((f[j,get]+w[i]>t[noget]) and (get<=k1)) or (noget>k2)
then begin
f[j+v[i],h]:=f[j,get]+w[i];
inc(get);
end
else begin
f[j+v[i],h]:=t[noget];
inc(noget);
end;
end;
end;
end;
total:=0;
for i:= 1 to f[vv,0] do
inc(total,f[vv,i]);
write(total);
end.
............

Answer 2

一看就是vijos...