嗯，改编自那道经典的01背包问题——采药。
题目链接：https://www.luogu.org/problemnew/show/P1616
与之间的采药不同，这里每种草药有无限多个，通常把这类问题称为完全背包问题。
每种草药并不唯一，会有若干个被放入背包，虽然看起来比01背包复杂很多，但实际上，他很容易转化为01背包问题。具体方法此处不再赘述，直接放一种简单有效的做法。在01背包代码中，优化空间复杂度后，我们是从T枚举到t[i]，之所以要这样做，是为了保证，dp[j]里存放的是考虑i-1株草药时的最大价值。假如我们从t[i]枚举到T，会怎样呢？就会导致，dp[j]里存放的是考虑过无数株的第i株草药后的最大价值，刚好符合完全背包的要求。
1 #include<cstdio> 2 inline int max(int a,int b) { 3 return a>b?a:b; 4 } 5 const int maxt=1e5+5,maxm=1e4+5; 6 int T,m,t[maxm],v[maxm],dp[maxt]; 7 int main() { 8 scanf("%d%d",&T,&m); 9 for(int i=1;i<=m;++i) scanf("%d%d",&t[i],&v[i]); 10 for(int i=1;i<=m;++i) 11 for(int j=t[i];j<=T;++j) 12 dp[j]=max(dp[j],dp[j-t[i]]+v[i]); 13 printf("%d",dp[T]); 14 return 0; 15 }
原文：https://www.cnblogs.com/Mr94Kevin/p/9595507.html
