51Nod1085 背包问题（01背包）

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

01背包，dp[i][j]表示在前i个物品中挑选放进容量为j的背包里的最大价值。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
struct thing{
  int w,p;
}a[10001];
int dp[102][10002];
int max(int a,int b)
{
  return a>b?a:b;
}
using namespace std;
int main()
{
  int n,m;
  cin>>n>>m;
  int i,j;
  for(i=1;i<=n;i++)
    cin>>a[i].w>>a[i].p;
  memset(dp,0,sizeof(dp));
  for(i=1;i<=n;i++)
    for(j=0;j<=m;j++)
    {
      dp[i][j]=(i==1?0:dp[i-1][j]);//如果物品不只一个，价值最少的也要跟物品减一的价值一样
      if(j>=a[i].w)
        dp[i][j]=max(dp[i][j],dp[i-1][j-a[i].w]+a[i].p);
    }
  cout<<dp[n][m]<<endl;
  return 0;
}