思路
很经典的 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; }