P1048 采药 动态规划
状态与状态转移方程

1 二维数组状态转移

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int t,m;
int dp[105][1005];
int v[105],w[105]; 
int main(){
    scanf("%d%d",&t,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&w[i],&v[i]);
    }
    dp[1][0]=0;
    for(int i=1;i<=m;i++){
        for(int j=0;j<=t;j++){
            dp[i][j]=dp[i-1][j];
            if(j-w[i]>=0){
                dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);//状态转移
            }
        }
    }
    printf("%d",dp[m][t]);
    return 0;
} 

核心代码（01背包）

特点：每样物品只能取一次

dp[1][0]=0;
    for(int i=1;i<=m;i++){
        for(int j=0;j<=t;j++){
            dp[i][j]=dp[i-1][j];
            if(j-w[i]>=0){
                dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);//状态转移
            }
        }
    }

2 滚动数组（一维数组优化）

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int t,m;
int dp[1005];
int v[105],w[105]; 
int main(){
    scanf("%d%d",&t,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&w[i],&v[i]);
    }
    dp[0]=0;
    for(int i=1;i<=m;i++){
        for(int j=t;j>=1;j--){
            if(j-w[i]>=0){
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
    } 
    printf("%d",dp[t]);
    return 0;
} 

针对每次的状态，我们都更新到第一行，而不是写到第二行，所以遍历的时候需要从后往前遍历，这样才不会替代前面的数据，核心代码中的j也就是时间（事实上是物品的体积）需要倒着输出

dp[0]=0;
    for(int i=1;i<=m;i++){
        for(int j=t;j>=1;j--){
            if(j-w[i]>=0){
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
    } 

均为01背包

#2019120500014-LG 采药

原文：https://www.cnblogs.com/liuziwen0224/p/11992418.html