题解 | #点菜问题#

#include <bits/stdc++.h>
using namespace std;

int main() {
    int totalWeight, type;
    while (cin >> totalWeight >> type) {

        int value[type], weight[type];
        for (int i = 0; i < type; i++) 
            cin >> weight[i] >> value[i];

        //构造dp数组
        int dp[type + 1][totalWeight + 1];

        for (int i = 0; i <= type; i++) {
            for (int j = 0; j <= totalWeight; j++) {
                if (i * j == 0) {
                    dp[i][j] = 0;//0容量的背包、或0价值的物品总价值为0
                } else { //物品有价值，或者背包有容量
                    //物品放不下时
                    if (weight[i-1] > j) {
                        dp[i][j] = dp[i-1][j];
                    } else { //放得下时，两者取大
                        dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]]+value[i-1]);
                    }
                }
            }
        }
        //输出dp中最大值
        int max = INT_MIN;
        for (int i = 0; i <= type; i++) {
            for (int j = 0; j <= totalWeight; j++) {
                if(dp[i][j]>max)
                    max = dp[i][j];
            }
        }
        cout<<max<<endl;
    }
}
// 64 位输出请用 printf("%lld")

经典01背包，分析一下状态转移方程：

如果背包容量为0/物品价值、重量为0，则总价值为0：dp[i][j] = 0

如果当前物品放不进背包，则总价值与不放该物品时的最大价值（即二维数组的上一行）一样，即：dp[i][j] = dp[i-1][j]

如果当前物品可以放进背包，则总价值看放进背包后价值是否上涨，是则放入，即：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]]+value[i-1])