与之间的采药不同, 这里每种草药有无限多个, 通常把这类问题称为完全背包问题.
每种草药并不唯一, 会有若干个被放入背包, 虽然看起来比 01 背包复杂很多, 但实际上, 他很容易转化为 01 背包问题. 具体方法此处不再赘述, 直接放一种简单有效的做法. 在 01 背包代码中, 优化空间复杂度后, 我们是从 T 枚举到 t[i], 之所以要这样做, 是为了保证, dp[j] 里存放的是考虑 i-1 株草药时的最大价值. 假如我们从 t[i] 枚举到 T, 会怎样呢? 就会导致, dp[j] 里存放的是考虑过无数株的第 i 株草药后的最大价值, 刚好符合完全背包的要求.
- #include<cstdio>
- inline int max(int a,int b) {
- return a>b?a:b;
- }
- const int maxt=1e5+5,maxm=1e4+5;
- int T,m,t[maxm],v[maxm],dp[maxt];
- int main() {
- scanf("%d%d",&T,&m);
- for(int i=1;i<=m;++i) scanf("%d%d",&t[i],&v[i]);
- for(int i=1;i<=m;++i)
- for(int j=t[i];j<=T;++j)
- dp[j]=max(dp[j],dp[j-t[i]]+v[i]);
- printf("%d",dp[T]);
- return 0;
- }
AC 代码
来源: http://www.bubuko.com/infodetail-2757052.html