四种基础背包问题

总结：背包问题是我接触的第一类DP问题，也是我之前很长时间都感到恐慌的一类题，在深入学习DP前，不得不牢固掌握这些基础问题，由此总结

---

>01背包

问题：有 N 件物品和一个容量为 V 的背包，每件物品有各自的价值且只能被选择一次,要求在有限的背包容量下，装入的物品总价值最大。

---

二维版本：

(1)状态表示：\(f[i][j]:在前i个物品中选择，且背包容量小于等于j的选法的集合\) \(属性:MAX\)

(2)状态计算：\(根据选不选第i个物品来划分集合\)

算法分析：
\(1.背包容量不够的时候(j < v[i])：没得选，因此前i个物品最优解即为前i-1个物品最优解，即 f[i][j] = f[i - 1][j]\)
\(2.背包容量够的时候，可以选，因此有两种情况：选或不选,选：f[i - 1][j - v[i]] + w[i],不选：f[i - 1][j],结果取其最大值\)

代码：

#include<iostream>
using namespace std;

const int N = 1010;

int f[N][N];
int v[N],w[N];


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 = 1;j <= m;j++)
     {
         f[i][j] = f[i - 1][j];
         if(j >= v[i]) f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + w[i]);
     }
     
     cout<<f[n][m]<<endl;
     return 0;
}

一维版本：二维的等价变形

(1)状态表示：\(f[j]:N件物品且背包容量j下的最优解\)

(2)背包容量j必须从m开始枚举

(3)为什么要逆序枚举？ 二维情况下,f[i][j]是由i-1轮的状态更新过来的。优化到一维后，如果还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用i - 1轮的状态，最后却用的是第i轮的。

---

\(eg:因为由于是滚动数组，我们必须是用上一层i - 1的状态，假设f[8] 是由 f[5] 更新过来，如果顺序枚举，则f[5]可能在f[8]之前被更新过，这样就是用到f[i][5]，显然不对。逆序枚举的话，f[8]同样由f[5]更新过来，但是f[5]还没进行第i轮的计算，因此计算的结果仍然是f[i-1][5]，可以说如果顺序枚举，前面的数会被污染。\)

代码

#include<iostream>
using namespace std;

const int N = 1010;

int f[N];
int v[N],w[N];


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;
}

输入优化

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
int f[MAXN];  // 

int main() 
{
    int n, m;   
    cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        int v, w;
        cin >> v >> w;      // 边输入边处理
        for(int j = m; j >= v; j--)
            f[j] = max(f[j], f[j - v] + w);
    }

    cout << f[m] << endl;

    return 0;
}

---

>完全背包

问题：有 N 件物品和一个容量为 V 的背包，每件物品有各自的价值且可以被任意次,要求在有限的背包容量下，装入的物品总价值最大。

---

二维版本：

(1)状态表示：\(f[i][j]:在前i个物品中选择，且背包容量小于等于j的选法的集合\) \(属性:MAX\)

(2)状态计算：\(根据第i个物品选几个来划分集合\)

算法分析：
\(选0个到选到放不下背包，即f[i][j] = max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,f[i-1][j-3v]+3w，.........)\)
\(上面f[i][j]的优化， f[i][j - v] = max(f[i-1][j-v]+f[i-1][j-2v]+w,f[i-1][j-3v]+2w,.......\)
我们发现，f[i][j]的右半部分在j-v的状态下已经算过了，因此可以得递推式：f[i][j] = max(f[i-1][j],f[i][j-v]+w)

代码：

#include<iostream>
using namespace std;

const int N = 1010;

int f[N][N];
int v[N],w[N];

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 = 1;j <= m;j++)
     {
         f[i][j] = f[i-1][j];
         if(j >= v[i])
          f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);
     }
     
    cout<<f[n][m]<<endl;
    return 0;
}

一维版本：二维的等价变形

(1)状态表示：\(f[j]:N件物品且背包容量j下的最优解\)

(2)背包容量j必须从0开始枚举

(3)顺序枚举 优化到一维后，顺序枚举，f[i][j]可由f[i-1][j]滚动过来，f[i][j-v[i]]+w[i]也是从根据当前i层状态更新，不会像01背包那样被污染，因此顺序枚举。

代码

#include<iostream>
using namespace std;

const int N = 1010;

int f[N];
int v[N],w[N];

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 = 1;j <= m;j++)
     {
         if(j >= v[i])
          f[j] = max(f[j],f[j-v[i]]+w[i]);
     }
     
    cout<<f[m]<<endl;
    return 0;
}

---

>多重背包

问题：有 N 件物品和一个容量为 V 的背包，每件物品有各自的价值且可以被有限次,要求在有限的背包容量下，装入的物品总价值最大。

---

朴素：

(1)状态表示：\(f[i][j]:在前i个物品中选择，且背包容量小于等于j的选法的集合\) \(属性:MAX\)

(2)状态计算：\(根据第i个物品选几个来划分集合,小于等于s[i]个\)

为什么多重背包不能像完全背包那样递推式优化，原因在于：完全背包受体积约束，多重背包受体积和物品个数约束

代码

#include<iostream>
using namespace std;
const int N = 110;
int v[N],w[N],s[N];
int f[N][N];
int n,m;

int main()
{
    cin>>n>>m;
    for(int i = 1;i <= n;i++)
     cin>>v[i]>>w[i]>>s[i];

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


    cout<<f[n][m]<<endl;
    return 0;
}

---

>分组背包

问题：有 N 组物品和一个容量为 V 的背包，每组物品有若干个，同一组内的物品最多只能选一个,要求在有限的背包容量下，装入的物品总价值最大。

---

算法分析：

(1)状态表示：\(f[i][j]:在前i个物品中选择，且背包容量小于等于j的选法的集合\) \(属性:MAX\)

(2)状态计算：\(根据第i组物品选第几个来划分集合\)

算法分析：
\(每组选一个或者不选，将问题转化成01背包\)

代码：

//二维
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 110;

int n,m;
int v[N][N],w[N][N],s[N];
int f[N][N];

int main()
{
    cin>>n>>m;
    for(int i = 1;i <= n;i++)
    {
        cin>>s[i];
        for(int j = 0;j < s[i];j++)
         cin>>v[i][j]>>w[i][j];
    }
    
    for(int i = 1;i <= n;i++)
     for(int j = 0;j <= m;j++)
     {
         f[i][j] = f[i-1][j];
         for(int k = 0;k < s[i];k++)
          if(v[i][k] <= j) f[i][j] = max(f[i][j],f[i-1][j-v[i][k]] + w[i][k]);
     }
    
    cout<<f[n][m]<<endl;
    return 0;
}

//一维优化空间后
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 110;

int n,m;
int v[N][N],w[N][N],s[N];
int f[N];

int main()
{
    cin>>n>>m;
    for(int i = 1;i <= n;i++)
    {
        cin>>s[i];
        for(int j = 0;j < s[i];j++)
         cin>>v[i][j]>>w[i][j];
    }
    
    for(int i = 1;i <= n;i++)
     for(int j = m;j >= 0;j--)
     {
         for(int k = 0;k < s[i];k++)
          if(v[i][k] <= j) f[j] = max(f[j],f[j-v[i][k]] + w[i][k]);
     }
    
    cout<<f[m]<<endl;
    return 0;
}