背包，WA60分

常规
1 
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1000000;
int n;
long long m,dp[MAX_N+1];
int main()
{
  cin >> n >> m;
  memset(dp,m+1,sizeof(dp));
  dp[0]=0;
  for(int i = 0;i < n;i++)
  {
    int v;
    long long w;
    cin >> w >> v;
    for(int i = MAX_N-v;i >= 0;i--)
    {
      dp[i+v]=min(dp[i+v],dp[i]+w);
    }
  }
  int ans=MAX_N;
  for(;ans >= 0;ans--)
  {
    if(dp[ans]<=m)
    {
      break;
    }
  }
  cout << ans;
  return 0;
}
2

题目ID：22503

3

这不对吧，dp好像是按字节赋值的，可以改成0x3f3f3f

1 个赞