点菜问题

思路

很经典的 0-1 背包问题，不太熟悉的可以去看一下背包九讲，报销经费的总额就是背包的容量，其实背包问题也是动态规划，我们用 dp[i][j] 表示前 i 种菜报销经费为 j 时的最大总评价分数，那么最后结果就是dp[N][C]

我们再来看看状态转移方程怎么写，对于第 i 种菜，我们可以选择也可以不选择

• 如果不选择的话：
• 如果选择的话：

则

#include<iostream>
#include<vector>

using namespace std;

int main(){
    int C, N;
    while(cin >> C >> N){
        int price, value;
        vector<pair<int, int>> prices;
        // 初始化
        for(int i = 0; i < N; i ++){
            cin >> price >> value;
            prices.emplace_back(price, value);
        }
        vector<vector<int>> dp(N + 1, vector<int>(C + 1, 0));
        for(int i = 1; i <= N; i ++){
            for(int j = 1; j <= C; j ++){
                // 如果点第 i 道菜，至少额度不小于第 i 道菜的价格
                if(j >= prices[i - 1].first)
                    dp[i][j] = max(dp[i - 1][j], 
                               dp[i - 1][j - prices[i - 1].first] + prices[i - 1].second);
                else dp[i][j] = dp[i - 1][j];
            }
        }
        cout << dp[N][C] << endl;
    }
    return 0;
}

但是我们肯定还是优化空间复杂度了，优化空间复杂度我们只需要去看状态转移方程，也就是 for 循环内部的等式，我们发现其实每次循环只时使用了上一行的两个元素，那我们可以新建两个变量去存储这两个元素，这是比较普通的想法。

我们会发现我们更新第 i 行第 j 个元素的时候我们是用不到第 j 个元素后面的部分的，那么如果我们逆序更新，就不会产生任何冲突了。

#include<iostream>
#include<vector>

using namespace std;

int main(){
    int C, N;
    while(cin >> C >> N){
        int price, value;
        vector<pair<int, int>> prices;
        // 初始化
        for(int i = 0; i < N; i ++){
            cin >> price >> value;
            prices.emplace_back(price, value);
        }
        vector<int> dp(C + 1, 0);
        for(int i = 1; i <= N; i ++){
            for(int j = C; j >= prices[i - 1].first; j --){
                // 如果点第 i 道菜，至少额度不小于第 i 道菜的价格
                dp[j] = max(dp[j], dp[j - prices[i - 1].first] + prices[i - 1].second);
            }
        }
        cout << dp[C] << endl;
    }
    return 0;
}