背包问题总结

• 1、0-1背包问题
• 2、完全背包问题
• 3、多重背包问题
• 4、分组背包问题
• 5、二维费用的背包问题

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

第 i i i 件物品的体积是 v i v_i vi​，价值是 w i w_i wi​。

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

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

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

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

数据范围
0 < N , V ≤ 1000 0 0 < v i , w i ≤ 1000 0 输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

解题代码：

#include
using namespace std;
const int MAX = 1005;
int w[MAX];
int v[MAX];
int f[MAX];
int main(){
    //此时应该需要做的就是 下标表示物品,f[j] 表示在j的容量之下 的最大价值 因此就可以这样进行优化
    int n, m;   
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) 
        cin >> v[i] >> w[i];
        //v 表示容量 w 表示体积
    for(int i =1;i<=n;i++){
        for(int j =m;j>=v[i];j--){
            // 没有加第i个的物品的时候的价值 
            f[j] = max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout< 
2、完全背包问题 
有 
    
     
      
       
        N
       
      
      
       N
      
     
    N 种物品和一个容量是 
    
     
      
       
        V
       
      
      
       V
      
     
    V 的背包，每种物品都有无限件可用。
 
第 
    
     
      
       
        i
       
      
      
       i
      
     
    i 种物品的体积是 
    
     
      
       
        
         v
        
        
         i
        
       
      
      
       v_i
      
     
    vi​，价值是 
    
     
      
       
        
         w
        
        
         i
        
       
      
      
       w_i
      
     
    wi​。
 
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
 输出最大价值。
 
输入格式
 第一行两个整数，
    
     
      
       
        N
       
       
        ，
       
       
        V
       
      
      
       N，V
      
     
    N，V，用空格隔开，分别表示物品种数和背包容积。
 
接下来有 
    
     
      
       
        N
       
      
      
       N
      
     
    N 行，每行两个整数 
    
     
      
       
        
         v
        
        
         i
        
       
       
        ,
       
       
        
         w
        
        
         i
        
       
      
      
       v_i,w_i
      
     
    vi​,wi​，用空格隔开，分别表示第 i 种物品的体积和价值。
 
输出格式
 输出一个整数，表示最大价值。
 
数据范围
 
    
     
      
       
        0
       
       
        <
       
       
        N
       
       
        ,
       
       
        V
       
       
        ≤
       
       
        1000
       
      
      
       0 
    
     
      
       
        0
       
       
        <
       
       
        
         v
        
        
         i
        
       
       
        ,
       
       
        
         w
        
        
         i
        
       
       
        ≤
       
       
        1000
       
      
      
       0 输入样例
 
4 5
1 2
2 4
3 4
4 5
 
输出样例：
 
10
 
解题代码：
 
#include
using namespace std;
const int N = 1e3+10;
int n,m;
int v[N],w[N];
int f[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 =v[i];j<=m;j++){
           f[j] = max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout< 
注意：01背包问题和完全背包问题区别：01背包问题必须从m开始遍历，完全背包问题从v[i]开始。
 
3、多重背包问题 
有 
    
     
      
       
        N
       
      
      
       N
      
     
    N 种物品和一个容量是 
    
     
      
       
        V
       
      
      
       V
      
     
    V 的背包。
 
第 
    
     
      
       
        i
       
      
      
       i
      
     
    i 种物品最多有 
    
     
      
       
        
         s
        
        
         i
        
       
      
      
       s_i
      
     
    si​ 件，每件体积是 
    
     
      
       
        
         v
        
        
         i
        
       
      
      
       v_i
      
     
    vi​，价值是 
    
     
      
       
        
         w
        
        
         i
        
       
      
      
       w_i
      
     
    wi​。
 
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
 输出最大价值。
 
输入格式
 第一行两个整数，
    
     
      
       
        N
       
       
        ，
       
       
        V
       
      
      
       N，V
      
     
    N，V，用空格隔开，分别表示物品种数和背包容积。
 
接下来有 
    
     
      
       
        N
       
      
      
       N
      
     
    N 行，每行三个整数 
    
     
      
       
        
         v
        
        
         i
        
       
       
        ,
       
       
        
         w
        
        
         i
        
       
       
        ,
       
       
        
         s
        
        
         i
        
       
      
      
       v_i,w_i,s_i
      
     
    vi​,wi​,si​，用空格隔开，分别表示第 
    
     
      
       
        i
       
      
      
       i
      
     
    i 种物品的体积、价值和数量。
 
输出格式
 输出一个整数，表示最大价值。
 
数据范围
 
    
     
      
       
        0
       
       
        <
       
       
        N
       
       
        ,
       
       
        V
       
       
        ≤
       
       
        100
       
      
      
       0 
    
     
      
       
        0
       
       
        <
       
       
        
         v
        
        
         i
        
       
       
        ,
       
       
        
         w
        
        
         i
        
       
       
        ,
       
       
        
         s
        
        
         i
        
       
       
        ≤
       
       
        100
       
      
      
       0 输入样例
 
4 5
1 2 3
2 4 1
3 4 3
4 5 2
 
输出样例：
 
10
 
解题代码：
 
#include
using namespace std;
const int N = 1e2+10;
int n,V;
int v[N],w[N],s[N];
int f[N][N];
int main(){
    scanf("%d%d",&n,&V);
    for(int i = 1;i<=n;i++){
        scanf("%d%d%d",&v[i],&w[i],&s[i]);
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=V;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]);
            }
        }
    }
    printf("%d",f[n][V]);
    return 0;
}

 
多重背包问题二进制优化
 
#include
using namespace std;
const int N = 3*1e4+10;
int v[N],p[N],f[N];
int n,V;
int main(){
    int total = 0;
    scanf("%d%d",&n,&V);
    int v1,w1,s1;
    for(int i = 1;i<=n;i++){
        scanf("%d%d%d",&v1,&w1,&s1);
        for(int j = 1;j= v[i];j--){
            f[j] = max(f[j],f[j-v[i]]+p[i]);
        }
    }
    cout< 
4、分组背包问题 
有 
    
     
      
       
        N
       
      
      
       N
      
     
    N 组物品和一个容量是 
    
     
      
       
        V
       
      
      
       V
      
     
    V 的背包。
 
每组物品有若干个，同一组内的物品最多只能选一个。
 每件物品的体积是 
    
     
      
       
        
         v
        
        
         
          i
         
         
          j
         
        
       
      
      
       v_{ij}
      
     
    vij​，价值是 
    
     
      
       
        
         w
        
        
         
          i
         
         
          j
         
        
       
      
      
       w_{ij}
      
     
    wij​，其中 
    
     
      
       
        i
       
      
      
       i
      
     
    i 是组号，
    
     
      
       
        j
       
      
      
       j
      
     
    j 是组内编号。
 
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
 
输出最大价值。
 
输入格式
 第一行有两个整数 
    
     
      
       
        N
       
       
        ，
       
       
        V
       
      
      
       N，V
      
     
    N，V，用空格隔开，分别表示物品组数和背包容量。
 
接下来有 
    
     
      
       
        N
       
      
      
       N
      
     
    N 组数据：
 
每组数据第一行有一个整数 
    
     
      
       
        
         S
        
        
         i
        
       
      
      
       S_i
      
     
    Si​，表示第 
    
     
      
       
        i
       
      
      
       i
      
     
    i 个物品组的物品数量；
 每组数据接下来有 
    
     
      
       
        
         S
        
        
         i
        
       
      
      
       S_i
      
     
    Si​ 行，每行有两个整数 
    
     
      
       
        
         v
        
        
         
          i
         
         
          j
         
        
       
       
        ,
       
       
        
         w
        
        
         
          i
         
         
          j
         
        
       
      
      
       v_{ij},w_{ij}
      
     
    vij​,wij​，用空格隔开，分别表示第 
    
     
      
       
        i
       
      
      
       i
      
     
    i 个物品组的第 
    
     
      
       
        j
       
      
      
       j
      
     
    j 个物品的体积和价值；
 输出格式
 输出一个整数，表示最大价值。
 
数据范围
 
    
     
      
       
        0
       
       
        <
       
       
        N
       
       
        ,
       
       
        V
       
       
        ≤
       
       
        100
       
      
      
       0 
    
     
      
       
        0
       
       
        <
       
       
        
         S
        
        
         i
        
       
       
        ≤
       
       
        100
       
      
      
       0 
    
     
      
       
        0
       
       
        <
       
       
        
         v
        
        
         
          i
         
         
          j
         
        
       
       
        ,
       
       
        
         w
        
        
         
          i
         
         
          j
         
        
       
       
        ≤
       
       
        100
       
      
      
       0 输入样例
 
3 5
2
1 2
2 4
1
3 4
1
4 5
 
输出样例：
 
8
 
#include
using namespace std;
const int N = 110;
int n,vv;
int v[N][N],w[N][N],s[N];
int f[N];
int main(){
    scanf("%d%d", &n, &vv);
    for(int i = 1 ;i <= n ;i ++){
        scanf("%d", &s[i]);
        for(int j = 0 ;j < s[i] ;j ++){
            scanf("%d%d", &v[i][j], &w[i][j]);
        }
    }
    for(int i = 1 ;i <= n ;i ++){
        for(int j = vv ;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]);
            }
        }
    }
    printf("%d",f[vv]);
    return 0;
}
 
5、二维费用的背包问题 
有 
    
     
      
       
        N
       
      
      
       N
      
     
    N 件物品和一个容量是 
    
     
      
       
        V
       
      
      
       V
      
     
    V 的背包，背包能承受的最大重量是 
    
     
      
       
        M
       
      
      
       M
      
     
    M。
 
每件物品只能用一次。体积是 
    
     
      
       
        
         v
        
        
         i
        
       
      
      
       v_i
      
     
    vi​，重量是 
    
     
      
       
        
         m
        
        
         i
        
       
      
      
       m_i
      
     
    mi​，价值是 
    
     
      
       
        
         w
        
        
         i
        
       
      
      
       w_i
      
     
    wi​。
 
求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
 输出最大价值。
 
输入格式
 第一行三个整数，
    
     
      
       
        N
       
       
        ,
       
       
        V
       
       
        ,
       
       
        M
       
      
      
       N,V,M
      
     
    N,V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。
 
接下来有 N 行，每行三个整数 
    
     
      
       
        
         v
        
        
         i
        
       
       
        ,
       
       
        
         m
        
        
         i
        
       
       
        ,
       
       
        
         w
        
        
         i
        
       
      
      
       v_i,m_i,w_i
      
     
    vi​,mi​,wi​，用空格隔开，分别表示第 
    
     
      
       
        i
       
      
      
       i
      
     
    i 件物品的体积、重量和价值。
 
输出格式
 输出一个整数，表示最大价值。
 
数据范围
 
    
     
      
       
        0
       
       
        <
       
       
        N
       
       
        ≤
       
       
        1000
       
      
      
       0 
    
     
      
       
        0
       
       
        <
       
       
        V
       
       
        ,
       
       
        M
       
       
        ≤
       
       
        100
       
      
      
       0 
    
     
      
       
        0
       
       
        <
       
       
        
         v
        
        
         i
        
       
       
        ,
       
       
        
         m
        
        
         i
        
       
       
        ≤
       
       
        100
       
      
      
       0 
    
     
      
       
        0
       
       
        <
       
       
        
         w
        
        
         i
        
       
       
        ≤
       
       
        1000
       
      
      
       0 输入样例
 
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6
 
输出样例：
 
8
 
#include 

using namespace std;

const int N = 1100;

int n, V, M;
int f[N][N];

int main()
{
    cin >> n >> V >> M;

    for (int i = 0; i < n; i ++ )
    {
        int v, m, w;
        cin >> v >> m >> w;
        for (int j = V; j >= v; j -- )
            for (int k = M; k >= m; k -- )
                f[j][k] = max(f[j][k], f[j - v][k - m] + w);
    }

    cout << f[V][M] << endl;

    return 0;
}