题解 | #点菜问题#
点菜问题
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; }