有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是v[i]，得到的价值是w[i] 。每件物品能取无限次，求解将哪些物品装入背包里物品价值总和最大。

#include <bits/stdc++.h>

using namespace std;

int n, V, ans, v[1005], w[1005];

int dp[1005]; 

// 状态定义 dp[i][j]表示讨论第i个物品，背包容量为j时，能取到的最大价值

// 状态转移方程 dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);

// 常用滚动数组优化一维 dp[j] = max(dp[j], dp[j-v[i]] + w[i]);

// 和 0-1背包不同是转移顺序变化

int main() {

    cin >> n >> V;

    for (int i = 1; i <= n; i++) {

        cin >> v[i] >> w[i];

    }

    for (int i = 1; i <= n; i++) {

        for (int j = v[i]; j <= V; j++) {

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

        }

    }

    cout << dp[V];

    return 0;

}