一维优化题解

由于 $\operatorname{dp}(i,j)$ 的值仅取决于上一层 $\operatorname{dp}(i-1,...)$的值，故我们可以尝试将dp转化为一维的。
以下是代码：

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

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

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<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 = cost; j>=costs[i] /* 如果当前的总消耗（背包容量）小于这个草药的消耗，跳过判断 */; j--) {
            dp[j] = max(dp[j], dp[j-costs[i]]+gets[i]);
            /*
            当前总消耗大于草药消耗时：
            选择该草药：则dp[j]值为选取前i-1个草药，总消耗为j-(草药消耗)时，最大值加上当前的草药价值
            不选择：则dp[j] = dp[j]
            */
        }
    }
    cout << dp[cost];
    return 0;
}