以上伪代码是背包九讲给出的 01背包 不做任何优化代码, N 位物品数量, V 为背包提及, Ci 为物品花费, Wi 为物品价值.

这道题是标准的 01背包, 所以我直接提交以上代码, 40 分.

#include <bits/stdc++.h>
using namespace std;
const int MAXM = 1000 + 5;
int t, m, w[MAXM], c[MAXM];
int dp[MAXM][MAXM];

int main() {
  cin >> t >> m;
  for (int i = 1; i <= m; i++)
    cin >> c[i] >> w[i];
  for (int i = 1; i <= m; i++)
    for (int j = c[i]; j <= t; j++) {
      dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i]);
    }
  cout << dp[m][t];
  return 0;
}

根据题解改了一下第二重循环就过了:

for (int j = 1; j <= t; j++) {
      dp[i][j] = dp[i - 1][j];
      if (j >= c[i])
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i]);
    }

不太明白原理, 跪请路过大佬帮忙解惑! (有样例就更好了