经典的01背包问题,萌新写法未考虑空间压缩,大佬看看笑笑就好○|￣|_(orz);

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 3e4 + 5;//钱最大数
const int H = 25;//物品最大数
/*
    @money:总钱数
    @n:物品的数目
    @cost[i]:每件物品的价格
    @weight[i]:每件物品的权重
    @dp[i][j]:考虑前i件物品,剩余钱数为j时的带权总和
    @ans:最后的结果
*/
int money,n,ans = 0;
int cost[H],weight[H],dp[H][N];
int main () {
    cin >> money >> n;
    for (int i = 1;i <= n;i++) cin >> cost[i] >> weight[i];
    for (int i = 1;i <= n;i++) {
        for (int j = money;j >= 0;j--) {
            if (j >= cost[i]) {
                dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - cost[i]] + cost[i] * weight[i]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
            if (i == n) ans = max(ans,dp[n][j]);
        }
    }
    cout << ans << endl;
    return 0;
}