noi 8462 大盗阿福代码编写

这里是一个可能的 NOI 8462 大盗阿福的代码实现：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1005;

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

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

这个代码使用动态规划算法，`dp[i][j]` 表示前 `i` 个物品在背包容量为 `j` 的情况下的最大价值。状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])

其中，`w[i]` 和 `v[i]` 分别表示第 `i` 个物品的重量和价值。最终答案为 `dp[n][m]`。