01背包问题

题目来源

https://www.acwing.com/problem/content/description/2/

思路

基本按照该文章 https://www.jianshu.com/p/a66d5ce49df5 思路码出的代码，感觉动态规划的本质还是在不断的打表，空间上还能用滚动数组优化，先挖个坑以后再补

代码

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 1005
int dp[MAXN][MAXN];//dp[n][v]前n个数在重量为v的情况下代表的价值

int main()
{
    int N,V;
    cin>>N>>V;
    int v[MAXN]={0};
    int w[MAXN]={0};
    for(int i = 1; i <= N; i ++)
    {
        cin>>v[i]>>w[i];
    }
    for(int i = 1; i <= N; i ++)//以1为初始值是因为默认dp[0][0]为0，方便代码书写 
    {
        for(int j = 1; j <= V; j ++)
        {
            if(j >= v[i])
            {
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);//转移方程 
            }
            else
            {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout<<dp[N][V];
    return 0;
}