【NOIP普及组模拟】采药

发布于 2019-04-07  5 次阅读


题目描述

凡凡是个聪明的孩子,今天他也要去采药,但是这次和聪聪不一样,他采的药是密度很大的,所以不仅要求背包的总空间V能放得下所采的药,还要求药草的总质量不能超过凡凡所能承受的范围M。
由于凡凡运动力惊人并且拥有敏锐的察觉力,所以他能发现N种珍惜的药材,对于每个药材凡凡都会精准地目测出其质量、体积和价值,现在要你做出一些取舍,使凡凡所能采到的药材的总价值最大。
注意:每种药材只有一个。

输入

第一行有三个整数M、V、N。
接下来有N行,每行三个整数,分别表示一种药材的质量、体积、价值。

输出

一行一个数,表示能获得的最大价值。

思路

其实这个和普通的背包没有什么区别,只是加多一维,多一个循环就可以了
当然也可以用二维做两次取更优解

const
  maxn=200;
  maxm=400;
var
  a,b,c:array[0..maxn] of longint;
  f:array[0..maxn,0..maxm,0..maxm] of int64;
  i,j,k,n,m,v:longint;

function max(x,y:int64):int64;
begin
  if x>y then max:=x else max:=y;
end;

begin
  assign(input,'medic.in');reset(input);
  assign(output,'medic.out');rewrite(output);
  readln(m,v,n);
  for i:=1 to n do
    readln(a[i],b[i],c[i]);
  for i:=1 to n do
    for j:=m downto 0 do
      for k:=v downto 0 do
        if (a[i]<=j) and (b[i]<=k) then
          f[i,j,k]:=max(f[i-1,j,k],f[i-1,j-a[i],k-b[i]]+c[i])
        else f[i,j,k]:=f[i-1,j,k];
  writeln(f[n,m,v]);
end.
]]>