洛谷P1048 采药
“01背包”
二维数组实现：
1 for(int i=1;i<=M;i++){ 2 for(int j=0;j<=T;j++){ 3 dp[i][j]=dp[i-1][j]; 4 if(j-t[i]>=0){ 5 dp[i][j]=max(dp[i-1][j-t[i]]+v[i],dp[i][j]); 6 } 7 } 8 } 9 printf("%d",dp[T][M]);
时间复杂度：$O(T*M)$
空间复杂度：$O(T*M)$
优化成一维数组：空间复杂度优化到（）
洛谷P1616 疯狂的采药
题意：
小A采药，共有T时间，共M种药，每种药的采药时间ti和采药价值vi给定，每种药可以采无限次，如何采药使价值最大而不超时间？
原文：https://www.cnblogs.com/liuziwen0224/p/11514833.html