题解 | #点菜问题#优化成一维
点菜问题
https://www.nowcoder.com/practice/b44f5be34a9143aa84c478d79401e22a
#include <iostream> #include <cstdio> using namespace std; int weight[2000]; int value[2000]; int dp[2000]; //dp[j]容量还有j, 当前价值为dp[j] int main() { int n, m; //n件物品, m为总容量 while (scanf("%d%d", &m, &n) != EOF) { for (int i = 1; i <= n; i++) { //从1开始 scanf("%d%d", &weight[i], &value[i]); } for (int i = 0; i <= m; i++) { //当啥都不选的时候,就算有再多的容量也没用 dp[i] = 0; } for (int i = 1; i <= n; i++) { for (int j = m; j >= weight[i]; j--) { dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } printf("%d\n", dp[m]); } }