POJ 2184：Cow Exhibition（01背包变形）

题意：有n个奶牛，每个奶牛有一个smart值和一个fun值，可能为正也可能为负，要求选出n只奶牛使他们smart值的和s与fun值得和f都非负，且s+f值要求最大。

分析：

一道很好的背包DP题，我们将smart值当作物品的体积，将fun值当作物品的价值，每个物品只能取一次，我们求对于每个背包体积求恰好装满该体积时价值和的最大值，也就是当所选奶牛smart值为某个值时，fun值的和的最大值。然后对于每个非负背包体积（smart值的和），判断对应最大价值（fun值的和）是否非负，如果非负说明这是一种可行方案，然后将两值相加，取所有可行方案中的s+f的最大值。

另外要注意既然背包体积恰好装满，所有下标非0的f数组元素要赋值为负无穷，但考虑到-maxlongint再减去一个数会出问题，故赋值为比它大一些的负数即可。

代码：

program exhibition;

var

  a,b:array[..]of longint;

  f:array[-..]of longint;

  n,i,m,j,h1,h2,ans:longint;

function max(x,y:longint):longint;

begin

  if x>y then max:=x else max:=y;

end;

begin

  readln(n);

  for i:= to n do

   begin

     readln(a[i],b[i]);

     if a[i]> then h1:=h1+a[i];

     if a[i]< then h2:=h2+a[i];

   end;

  for i:=h2 to h1 do if i<> then f[i]:=-(maxlongint) div ;

  for i:= to n do

   if a[i]> then

   begin

   for j:=h1 downto h2 do

    if j-a[i]>=h2 then f[j]:=max(f[j],f[j-a[i]]+b[i]) else break;

   end

  else

   begin

   for j:=h2 to h1 do

    if j-a[i]<=h1 then f[j]:=max(f[j],f[j-a[i]]+b[i]) else break;

   end;

  for i:= to h1 do

   if f[i]>= then ans:=max(ans,f[i]+i);

  writeln(ans);

end.

巴特西

POJ 2184：Cow Exhibition（01背包变形）

最新文章

热门文章