【正经题解】飞马踏燕Gold King2

#include <iostream>
using namespace std;

const int MAX_N = 200005;

int dp[MAX_N]; // dp数组用于存储状态转移的结果
int v[MAX_N];  // v数组用于存储商品体积
int c[MAX_N];  // c数组用于存储商品价值

int main() {
    int n;
    cin >> n;

    // 输入商品体积
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }

    // 输入商品价值
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }

    // 动态规划
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 1000; j++) {
            if (j >= v[i]) {
                dp[j] = max(dp[j], c[i] + dp[j - v[i]]);
            }
        }
    }

    // 输出结果
    cout << dp[1000];

    return 0;
}