0/1背包

这道题可以说是dp入门题

当年还是小学6年级的时候打了好久暴力，后来才发现简单得很。

用一个滚动数组维护可以省一维空间。

dp[i]=dp[k]+value{cost<=k<=w}

value表示价值,cost表示花费，w表示背包容量。

#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
const int MAXM=207;
using namespace std;
int dp[MAXM],n,m;
int main()
{
    memset(dp,0,sizeof(dp));
    scanf("%d%d",&m,&n);
    int x,y;
    for (int i=0;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        for (int j=m;j>=x;j--)
        {
            dp[j]=max(dp[j],dp[j-x]+y);
        }
    }
    printf("%d",dp[m]);
}