本篇是背包问题

01背包，以下是2维dp代码

#include<iostream>
#include<vector>
using namespace std;

/*
dp[i][j]表示，在选取前i个草药，总消耗为j的情况下的总获得（价值）
*/

vector<vector<long long> > dp;
/*
costs[i] 表示输入第i个草药的消耗（时间）
gets[i] 表示输入第i个草药的获得（价值）
*/
vector<int> costs, gets;

int cost, get;
int main() {
    cin >> cost >> get;
    costs = vector<int>(cost+1, 0);
    gets = vector<int>(get+1, 0);
    dp = vector<vector<long long> >(get+1, vector<long long>(cost+1, 0));
    for (int i = 1; i<=get; i++) 
        cin >> costs[i] >> gets[i];
    
    for (/* 当前选取了前i个草药 */int i = 1; i<=get; i++) {
        for (/* 当前背包容量（总消耗）为j */int j = 1; j<=cost; j++) {
            /* 最大化利益 */
            if (j < costs[i])
                dp[i][j] = dp[i-1][j];
            // 如果当前的总消耗（背包容量）小于这个草药的消耗，跳过判断
            else 
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-costs[i]]+gets[i]);
            /*
            当前总消耗大于草药消耗时：
            选择该草药：则dp[i][j]值为选取前i-1个草药，总消耗为j-(草药消耗)时，最大值加上当前的草药价值
            不选择：则dp[i][j] = dp[i-1][j]
            */
        }
    }
    cout << dp[get][cost];
    return 0;
}