C++ 实现 0-1 背包问题 | 最优解算法

#include #include using namespace std;

const int MAXN = 1005;

int n, c; int w[MAXN], v[MAXN]; int dp[MAXN][MAXN];

int main() { cin >> n >> c; for (int i = 1; i <= n; i++) { cin >> w[i] >> v[i]; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= c; j++) { if (j < w[i]) { dp[i][j] = dp[i-1][j]; } else { dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]); } } } cout << dp[n][c] << endl; return 0; }