题解 | #点菜问题#
点菜问题
https://www.nowcoder.com/practice/b44f5be34a9143aa84c478d79401e22a
用一维数组来优化
#include<iostream>
#include<vector>
#include<algorithm>
#include<limits>
using namespace std;
int main() {
int c, n;
while(cin>>c>>n){
int p[101];
int v[101];
for (int i = 0; i < n; i++){
cin >> p[i] >> v[i];
}
int dp[1001];
//dp[x][y] 在总额度不超过x块的情况下，考察0-y-1号商品的最大评分
for (int y = 0; y <= c; y++) {
dp[y] = 0;
}
for(int i=0;i<n;i++){
for(int j=c;j>=p[i];j--){
dp[j] = max(dp[j],dp[j-p[i]] + v[i]);
}
}
cout << dp[c] << endl;
}
return 0;
}
查看1道真题和解析