背包问题

01背包问题（每个物品只能拿0或1次）

朴素写法

for(int i = 1; i <= n; i++) 
        for(int j = 1 ; j <= m ; j++)
            if(j < v[i]) f[i][j] = f[i-1][j];
            else
            f[i][j] = max(f[i-1][j], f[i-1][j - v[i]] + w[i]);

如何优化呢？
将状态f[i][j]优化到一维f[j]

1.注意枚举背包容量j必须从m开始。

2.为什么一维情况下枚举背包容量需要逆序？
在二维情况下，状态f[i][j]是由上一轮i - 1的状态得来的，f[i][j]与f[i - 1][j]是独立的。而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态。

3.简单来说，一维情况正序更新状态f[j]需要用到前面计算的状态已经被「污染」，逆序则不会有这样的问题。

状态转移方程为：f[j] = max(f[j], f[j - v[i]] + w[i] 。

优化（一维）后代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1005;
int v[N];    // 体积
int w[N];    // 价值 
int f[N];  // f[i][j], j体积下前i个物品的最大价值 

int main() 
{
    int n, m;   
    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] << endl;

    return 0;
}

完全背包问题（每件物品有无限个）

朴素写法

for(int i = 1 ; i <= n ; i++)
  for(int j = 0 ; j <= m ; j++)
     for(int k = 0 ; k * v[i] <= j ; k++)
         f[i][j] = max(f[i-1][j] , f[i-1][j-v[i]*k] + w[i]*k);

优化后（去k，化一维）后代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1005;
int v[N];    // 体积
int w[N];    // 价值 
int f[N];  // f[i][j], j体积下前i个物品的最大价值 

int main() 
{
    int n, m;   
    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 = v[i]; j<=m; j++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}

多重背包问题(每个物品最多有si个，每个物品对应的si不一样)