ruiqi 的小小sky

金明的预算方案(ruiqi)

　　如果看过普及组试卷就会发现，对应的第二个题目，也是一个样的背景，提高组只是多了个“主件附件”的的关系，如果去掉这一点，就全没区别了。也就成了经典的背包问题了。也就是多了这么一点，考试的时候就晕了。不知道怎么做了。后来才发现是个很简单的dp题目。可惜我当时没做出来。
　　草率的审题，可能会得到这样的算法：dp，对每一个物品做两种决策，取与不取。如果取，满足两个条件：1.要么它是主件，要么它所属的主件已经在包里了。2.放进去后的重要度与价格的成绩的总和要比没放进时的大。这两个条件缺一不可的。于是呼，得到如下的动规方程：
　　　f[i,j]:=f[i-1,j];
if (i为主件or i的附件在包中）and (f[i,j]<f[i,j-v]+v*w)
then f[i,j]:=f[i,j-v]+v*w;
　　我们来分析一下复杂度，空间：dp的阶段为n^2,对与每一个阶段都要记录该状态下在包中的物品有哪些（因为要确定附件的主件是否在包中)，每个阶段的记录都要O(n)的空间，所以总的就是O(n^3)。时间，一个dp，n^2的外层循环，内部用布尔量加个主附件的对应数组，为O(1)，和起来就为O(n^2)的复杂度。
　　可以看的出，时间的需求为32000*60，不成问题。空间32000*60*60，大约要7.5M的空间，在64M的要求下是完全可以的过的。如果用上题目中的一个很隐秘的条件：“每件物品都是10元的整数倍”，就可以把速度在提高十倍。


　　细细的看题目，还一个很重要的条件我们还没用：“每个主件可以有０个，１个或２个附件”。这貌似不起眼的一句话，却给我们降低复杂度提供了条件。想一想，为什么题目要对附件的个数做限制呢，明显是在降低难度。
　　对于一套物品（包含主件，所以的附件），我们称为一个属类，对一个属类的物品的购买方法，有以下５种：
　　　　１.一个都不买
　　　　２.主件
　　　　３.主件＋附件１
　　　　４.主件＋附件２
　　　　５.主件＋附件１＋附件２
　　这五种购买方法也是唯一的五种方法，也就是说对一属类的物品，我们只有上述的５种购买方法。
　　于是我们很自然的就会想到把物品按物品的属类捆在一起考虑。这样我们把物品的属类作为dp的状态。可以得到如下的dp方程：
　　f[i,j]=max{f[i-1,j];
  f[i-1,j-v[i,0]]+v[i,0]*w[i,0];
  f[i-1,j-v[i,0]-v[i,1]]+v[i,0]*w[i,0]+v[i,1]*w[i,1];
  f[i-1,j-v[i,0]-v[i,2]]+v[i,0]*w[i,0]+v[i,2]*w[i,2];
  f[i-1,j-v[i,0]-v[i,1]-v[i,2]]+v[i,0]*w[i,0]+v[i,1]*w[i,1]+v[i,2]*w[i,2];}
很显然时间复杂度为O(n^2)，空间复杂度为O(n^2)，加上利用“每件物品都是10元的整数倍”除以10的优化，本题就很完美的解决了。


附程序：

program Qi(input,output);
type
node=record
  u:integer;
  v:array[0..2] of integer;
  p:array[0..2] of integer;
  end;
var
n,m,k:integer;
w:array[1..60] of node;
f:array[0..60,0..3200] of longint;
g:array[1..60] of integer;
procedure init;
var
i,j:integer;
vx,px,qx:array[1..60] of integer;
begin
readln(n,m); k:=0;
for i:=1 to m do
begin
  readln(vx,px,qx);
  if qx=0
  then begin
    k:=k+1; g:=k;
    with w[k] do
    begin
    u:=0;
    v[0]:=vx; p[0]:=px;
    for j:=1 to 2 do begin v[j]:=0; p[j]:=0; end;
    end;
    end;
end;
for i:=1 to m do
if qx<>0
  then begin
    with w[g[qx]] do
    begin
    u:=u+1;
    v:=vx; p:=px;
    end;
    end;
for i:=1 to k do
with w do
  begin
  for j:=0 to 2 do write('(',v[j],',',p[j],') ');
  writeln;
  end;
end;
procedure doit;
var
i,j:integer;
begin
fillchar(f,sizeof(f),0);
for i:=1 to k do
with w do
  begin
  for j:=1 to n do
  begin
    f[i,j]:=f[i-1,j];
    if (j>=v[0]) and (f[i,j]<f[i-1,j-v[0]]+v[0]*p[0])
    then f[i,j]:=f[i-1,j-v[0]]+v[0]*p[0];
    if (j>=v[0]+v[1]) and (f[i,j]<f[i-1,j-v[0]-v[1]]+v[0]*p[0]+v[1]*p[1])
    then f[i,j]:=f[i-1,j-v[0]-v[1]]+v[0]*p[0]+v[1]*p[1];
    if (j>=v[0]+v[2]) and (f[i,j]<f[i-1,j-v[0]-v[2]]+v[0]*p[0]+v[2]*p[2])
    then f[i,j]:=f[i-1,j-v[0]-v[2]]+v[0]*p[0]+v[2]*p[2];
    if (j>=v[0]+v[1]+v[2]) and (f[i,j]<f[i-1,j-v[0]-v[1]-v[2]]+v[0]*p[0]+v[1]*p[1]+v[2]*p[2])
    then f[i,j]:=f[i-1,j-v[0]-v[1]-v[2]]+v[0]*p[0]+v[1]*p[1]+v[2]*p[2];
  end;
  end;
end;
procedure print;
begin
writeln(f[k,n]);
end;
begin
init;
doit;
print;
end.

                                                                ruiqi说：谢谢牛们的支持！


附件： 金明的预算方案.rar (5 K)