0-1背包问题

0-1背包：
有N 件物品和一个容量是V 的背包。每件物品只能使用一次。
第 i 件物品的体积是vi，价值是wi。

优化一维：

for(int i=1;i<=n;i++)
	for(int j=m;j >= V[i];j--){
	//if(j >= V[i]) f[i][j] = max( f[i][j] , f[i-1][j-V[i]] + W[i]);
	//因为max 右侧用到的是 i-1 层 但是如果我们去掉了第一维，那么用到的是f[i][j - v[i]]这是不对的，因为正序枚举用的是本轮的，
	//那如何保证用到的f[j - v[i]]是上一轮即f[i - 1][j - v[i]]呢，
	//我们可以倒序枚举，即先枚举较大的，因为v[i] >= 0，所以j >= j - v[i]，所以先计算较大的f[j]，即可保证使用的f[j - v[i]]是上一轮的f[i][j - v[i]]
	f[j] = max( f[j] , f[j-V[i]] + W[i]);
}

可以做一下下面的题。
Acwing 2. 01背包问题

参考代码：
使用二维的

#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
int f[N][N];
int n,m;
PII a[N];

int main(){
    cin>>n>>m;
    for(int i = 1;i <= n;i++){
        int v,w;
        cin>>v>>w;
        a[i] = {v,w};
    }
    f[0][0] = 0;
    //计算背包问题
    for(int i = 1;i <= n; i++){
        //枚举背包的体积
        for(int j = 1; j <= m;j++){
            //不选当前的物品
            int v = a[i].first, w = a[i].second;
            f[i][j] = f[i - 1][j];
            //选
            if(j >= v) f[i][j] = max(f[i][j],f[i - 1][j - v] + w);
            
        }
    }
    cout<<f[n][m];
    return 0;
}

使用一维：

#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
int f[N];//体积是j的最大价值
int n,m;
PII a[N];

int main(){
    cin>>n>>m;
    for(int i = 1;i <= n;i++){
        int v,w;
        cin>>v>>w;
        a[i] = {v,w};
    }
    f[0] = 0;
    //计算背包问题
    for(int i = 1;i <= n; i++){
        int v = a[i].first, w = a[i].second;
        //枚举背包的体积
        for(int j = m; j >= v;j--){

            f[j] = max(f[j],f[j - v] + w);
            
        }
    }
    cout<<f[m];
    return 0;
}