动态规划之0-1背包问题

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

#include <iostream>
using namespace std;

#define MAXN 105
#define MAXW 10005

struct project
{
    int v, w;
} p[MAXN];

int dp[MAXN][MAXW] = {0};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N, W;
    cin >> N >> W;

    for (int i = 1; i <= N; ++i)
        cin >> p[i].v >> p[i].w;

    for (int i = 1; i <= N; ++i)
    {
        for (int j = 0; j <= W; ++j)
        { 
            if (j - p[i].w >= 0)//
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - p[i].w] + p[i].v);
            else    //装不下这个物品
                dp[i][j] = dp[i - 1][j];
        }
    }

    cout << dp[N][W] << endl;
}