题目描述

此题是经典的01背包问题，此题最好想的做法就是用f[i][j]二维数组来做了，i表示取到第i个物品，j表示空间，f[i][j]表示的状态是取到第i个物品（第i个物品可要可不要），此时的空间大小为j的情况下的最大价值。f[i][j] = max(f[i-1][j - v[i]] + w[i], f[i][j])。
第二种方法就是就是变成一维来做，第一维枚举物品类型，第二维从大到小枚举空间。之所以从大到小为什么是从大小呢？可以想到，如果是从小到大，则意味着当j大于等于i的两倍的时候，f[j]里面可能包含两个i，不符合01背包的要求。

算法1

(暴力枚举) $O(nm)$

nm指的第一层循环枚举物品类型（此处对于物品不需要做任何形式的排序），第二轮从大到小枚举空间。

C++ 代码

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

int main()
{
    int N, V;
    cin >> N >> V;
    vector<int> vi(N, 0);
    vector<int> wi(N, 0);

    vector<int> f(V + 1, 0);

    for(int i = 0; i < N; i ++ ) cin >> vi[i] >> wi[i];

    for(int i = 0; i < N; i ++ )
        for(int j = V; j >= vi[i]; j -- )
        {
            f[j] = max(f[j - vi[i]] + wi[i], f[j]);
            //cout << f[j] << ' ' << endl;
        }
    int res = 0;
    for(int i = 0; i <= V; i ++ ) res = max(res, f[i]);
    cout << res << endl;
    return 0;
}