NYOJ 860 又见01背包(思维)

#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1000000;
int dp[MAXN];
int w[200];
int v[200];
int m,p;
int main()
{
    while(cin>>m>>p){
      int sum = 0;
    for(int i=0;i<m;i++){
      cin>>w[i]>>v[i];
      sum+=v[i];
    }
    memset(dp,MAXN,sizeof(dp));      // 要求最小值，需要都初始化为最大值
    dp[0] = 0;                       // 这个符合情况，需要单独把dp[0]初始化为0
    for(int i=0;i<m;i++){            // 01背包按重量存入dp
      for(int j=sum;j>=v[i];j--){
        dp[j] = min(dp[j],dp[j-v[i]]+w[i]);
      }
    }
    for(int i=sum;i>=0;i--){    // 从价值最大开始往后遍历
      if(dp[i] <= p){           // 当遍历到第一个dp[i] <= p 时刚好符合题意，输出i即可
        cout<<i<<endl;
        break;
      }
    }
  }
  return 0;
}
/***
   [来源] NYOJ 860
   [题目] 又见01背包
   [大意]
      虽然是一个01背包题，但是数据范围太大，跑下来肯定会TLE所以要换种方式去做，因为要求重量不超过W的最大价值，可以
      反着求最小重量，对应的就是其最大价值。详细看代码注释。
    [输入]
      4 5
      2 3
      1 2
      3 4
      2 2
    [输出]
      7
  */