洛谷 P1616——疯狂地采药 完全背包问题

Solution：

这是一道完全背包问题。因为每种药物的数量无限，所以我们就不能继续使用解决01背包问题的方法。完全背包需要正推，因为每种物品可以装的数量在0~m/cost[i]之间，所以我们要把j从cost[i]开始，一直递增到m。

代码如下：

#include<iostream>
#include<math.h>
#define MAX 100005
using namespace std;

int n,m;//n为草药数，m为总时间
int dp[MAX];
int cost[MAX];
int w[MAX];

int main(){
  cin>>m>>n;
  for(int i=0;i<MAX;i++){
    dp[i]=0;
    cost[i]=0;
    w[i]=0;
  }
  for(int i=0;i<n;i++){
    cin>>cost[i]>>w[i];
  }
  for(int i=0;i<n;i++){
    for(int j=cost[i];j<=m;j++){
        dp[j]=max(dp[j],dp[j-cost[i]]+w[i]);
    }
  }
  cout<<dp[m];
  return 0;
}