题解 | 采药

// 经典的动态规划, 0-1背包题目, 下面是最重要的三个分析 (未优化版本, 更好理解, 直接套模板): 
// dp[i][j] 表示i个草药, j的总时间, 能采到的草药的最大总价值

// 状态转移方程: 
// 当j-w[i] >= 0时, dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
// 否则, dp[i][j] = dp[i-1][j];

// 边界条件: dp[i][0] = 0, dp[0][j] = 0, (0 <= i <= m, 0 <= j <= t)

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXT = 1001;
const int MAXM = 101;

int dp[MAXM][MAXT];
int w[MAXM];
int v[MAXM];

int main() {
    int t, m;
    while (scanf("%d%d", &t, &m) != EOF) {
        // 初始化
        memset(dp, 0, sizeof(dp));        
        for (int i = 1; i <= m; i++) {
            scanf("%d%d", &w[i], &v[i]);
        }

        // 动态规划
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= t; j++) {
                if (j >= w[i]) {
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        printf("%d\n", dp[m][t]);
    }
    return 0;
}