此题代码未必正确，今天只是看到了这个题目，但是对应的给出的题目链接进不去，所以代码没提交过。

参考文献：

https://blog.csdn.net/u013050857/article/details/43345785

题目

描述
有n个重量和价值分别为wi 和 vi 的 物品，从这些物品中选择总重量不超过 W的物品，求所有挑选方案中物品价值总和的最大值。
　　1 <= n <=100
　　1 <= wi <= 10^7
　　1 <= vi <= 100
　　1 <= W <= 10^9

输入多组测试数据。
每组测试数据第一行输入，n 和 W ，接下来有n行，每行输入两个数，代表第i个物品的wi 和 vi。

输出满足题意的最大价值，每组测试数据占一行。

样例输入

4 5
2 3
1 2
3 4
2 2

样例输出

7

此题最大收获

此题一看就是最基本的01背包问题，但是此题与之前的01背包问题不同的地方就是它这题的体积的数据范围非常的大，而价值的范围非常的小，如果像之前一样枚举体积的话，则会TLE。所以此题的收获便是原来同样可以通过枚举价值。来计算01背包问题。

由于此题的体积的数据范围特别大，而如果像往常一样枚举体积的话会TLE，所以我们可以通过枚举价值，
通过不同的价值去计算对应的价值下所需要的最小体积。

求出对应的所有f[][]后

随后从大价值往小价值不断枚举，看是否有对应的价值下，所需要的体积在最大体积的范围内
如果在最大体积的范围内，则说明这个价值是可以存在的情况。

而f[][] == 0x3f3f3f3f的含义是没有任何一种选择能够到达这个价值的情况。

f[i][j]的状态表示:从前i个物品中选，总价值恰好为j的情况下最小的重量值

状态计算：

不要a[i]: f[i - 1][j];
要a[i]:f[i - 1][j - v[i]] + w[i];

代码实现

/*
f[i][j]:从前i个物品中选，总价值恰好为j的最小重量
*/


# include <iostream>
# include <cstring>
using namespace std;

const int N = 110 , V = 100 * 100 + 10; //最多有100个物品，每个物品最大价值100

// int f[N][V];  //二维
int f[V]; //一维

int w[N],v[N];  //w[]为体积，v为价值

int n,m;  //n为物品数，m为最大重量

int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 1 ; i <= n ; i++)
    {
        scanf("%d %d",&w[i],&v[i]);
    }

    /*
    memset(f,0x3f,sizeof f);
    f[0][0] = 0;  //前0个物品，价值恰好为0的情况就是一个物品都没有，所以为0.
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 0 ; j <= V ; j++)
        {
            f[i][j] = f[i - 1][j];
            if(j >= v[i])
            {
                f[i][j] = min(f[i][j],f[i - 1][j - v[i]] + w[i]);
            }
        }
    }
    //如果f[][]的值为0x3f3f3f3f,则代表没有这种情况
    for(int i = V - 1 ; i >= 0 ; i--)
    {
        if(f[n][i] <= m)
        {
            printf("%d\n",i);
            break;
        }
    }
    */

    // 一维
    memset(f,0x3f,sizeof f);
    f[0] = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = V ; j >= v[i] ; j--)
        {
            f[j] = min(f[j],f[j - v[i]] + w[i]);
        }
    }

    for(int i = V - 1; i >= 0 ; i--)
    {
        if(f[i] <= m)
        {
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}