关于采药问题 [复制链接]

这个和一道普及组复赛题 猴子才花生一样 应该是2002年的

啊哈哈!

我终于找到我会做的题了
我的标程,测试数据全过!

program noip20053medic;
const maxn=1100;maxm=120;
var
a:array[0..maxn] of longint;
w,c,v,t:array[0..maxm] of longint;
n,m,i,j,ans:longint;

procedure first;
begin
  assign(input,'medic.in');
  assign(output,'medic.out');
  reset(input);rewrite(output);
  readln(n,m);
  for i:=1 to m do
    begin
      read(v[i]);readln(t[i]);
      w[i]:=v[i];c[i]:=t[i];
    end;
end;

begin
  first;
  for i:=1 to m do
    for j:=n downto w[i] do
      if a[j]<a[j-w[i]]+c[i] then a[j]:=a[j-w[i]]+c[i];
  ans:=a[n];
  writeln(ans);
  close(input);close(output);
end.

就是这样的,可以解0-1背包!

贪心法

我也不会

动态规划！0、1背包的变种，简单！

O(nw)的迭代。。。

#include"fstream.h"
#include"iostream.h"
main()
{
    fstream fin,fout;
    fin.open("medic.in",ios::in);
    fout.open("medic.out",ios::out);
    int time,kind,i,j,v[101],t[101],s[101][1001];//v=价值，t=时间，s[i][j]表示总共j时间，前i种（数组从0开始）药得到的最大价值
    fin>>time>>kind;
    for(i=0;i<kind;i++)fin>>t[i]>>v[i];
    for(i=0;i<=time;i++)
        s[0][i]=0;
    for(i=0;i<kind;i++)
    {
        for(j=1;j<=time;j++)
        {
            s[i+1][j]=s[i][j];
            if(t[i]<=j)if(s[i][j-t[i]]+v[i]>s[i+1][j])//在时间还够的条件下，取二者中较优的情况
                s[i+1][j]=s[i][j-t[i]]+v[i];
        }
    }
    fout<<s[kind][time]<<endl;
}
我写的C++的源代码，用DP，全部通过了
写的不好，见笑了

dp!

...

这个是不是01背包的动态规划??