刚一看这道题以为是01背包的裸题，TLE了一次后发现这是一道拐了个弯的裸题，题中给的物品重量范围太大了，所以我们可以换种思路，把最大价值求出来，然后在dp中用价值去存重量，然后价值从大到小遍历找出第一个不大于题中给的重量，然后输出价值即可。
AC代码：
代码语言：javascript复制#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
*/
