题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤1000
0<vi,wi≤1000

样例

输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8

算法1

(二维数组) $O(n^2)$

本质就是将后面运算可能用到的值保存起来，核心思想在于找到递推方程式，这个用闫氏DP分析就可以很好的解决。
之后就是遍历了，其实也就是相当于一个枚举，将所有的情况罗列出来。
状态转移方程：f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+w[i]);

O(m*n)

y总模板

C++ 代码

`#include<iostream>
#include<algorithm>
using namespace std ;
const int  N=1010;
int w[N],v[N],f[N][N]; 
int m,n;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];
            if(v[i]<=j) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    cout<<f[n][m];
    return 0;
}`

算法2

(一维优化) 空间复杂度O(N)

这里将是这篇题解存在的意义：思考数天之后对一维优化的理解。

以此为案例进行说明讲解。

在这里我们可以看到的是，我们第i行的计算只和i-1行有关，所以我们无需第一维来存储行数，所以可直接将第一维删掉。但是直接删除存在一些计算时的问题。状态转移方程：f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+w[i]);若是直接删除之后便成了f[j]=max(f[j],f[j-v[i]+w[i])。

这很明显不是等价的，因为我们是这时候很明显就是同一行的更新同一行了，我们的定义就是上一行更新本行。所以我们在遍历重量的时候只需要将重量逆序遍历即可。

那么问题就转化成为了为什么逆序遍历重量就可以保证是上一行的更新本行的呢。答案其实还是在递推式里面：f[j]=max(f[j],f[j-v[i]+w[i])。

这里我们可以很明显的看到j-v[i]是严格小于j的，如果是顺序遍历的话，那么势必会将本行前面的数据先更新，然后这些更新的数据会更新后面的数据，这时候与我们的定义相悖；若是采用逆序遍历的话，前面的数据仍然是使用上一行来的，符合我们的定义。

时间复杂度 O(m*n)

参考文献 各种百度

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std ;
const int  N=1010;
int w[N],v[N],f[N];
int m,n;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
             f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];
    return 0;
}