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

不懂~~~~~~~~~~~~

...
贪心只能局部最优,学过动规没？

DP!
去年我做的时候用的贪心，才得20分

背包问题改了一下嘛　怎么会看不懂呢　比背包还简单

晕哦，这位妇女侠能否解读一下这份程序。特别是精华部分，谢谢

什么态度？！“妇女侠”是什么东东啊！！

把数字带进去试试不就知道了么。
因为不能重复，所以就边读边判断加上该物品价值是否大于不加嘛

贪心肯定不行的，是去年用的是深搜，拿了40分！这是01背包问题！

最明显的DP题啊!

我会,不过是C++
用动态规划
#include<fstream>
using namespace std;
ifstream fin("medic.in");
ofstream fout("medic.out");
int t,m,ans;
int countline[1001];
struct data
{
    int time;
    int price;
}med[101];

main()
{
  int indata();
  int count();
  indata();
  count();
  fout<<ans; 
}

int indata()
{
  int i;
  fin>>t>>m;
  for(i=1;i<=m;i++)
    fin>>med[i].time>>med[i].price;
}
int count()
{
  int i,j,k;   
  memset(countline,0,sizeof(countline)) ;
  for(i=1;i<=m;i++)
    for(j=t;j>=1;j--)
      {
        if (j>=med[i].time&&med[i].price+countline[j-med[i].time]>countline[j])
          countline[j]=med[i].price+countline[j-med[i].time];
      }
  ans=countline[t];
   
}