背包问题 01背包 完全背包 多重背包 分组背包

背包问题 01背包 完全背包 多重背包 分组背包

背包问题

01背包问题完全背包问题多重背包问题分组背包问题总结

01背包问题

问题描述：给定N个物品，每个只有一件，每个物品都有相应的价值w与体积v，给定体积为M的背包，求背包所能装的最大物品价值。

一般思路分析：每个物品分为选和不选两种方案，所以一共有2的n次方种方案，方案数量特别多，暴力做法不可取。

DP思路分析：用 f[ i ][ j ] 表示在前i个物品中选择方案，且选择方案总体积不超过j时的最大价值。那么 f[N][M] 就表示在前N个物品中选择，且体积不超过M的最大价值，也即题目要求的最大价值。
对 f[ i ][ j ] 可以分成两种情况分析：

情况一： f[ i ][ j ] 中选择了第 i 个物品，那么 f[ i ][ j ] 如下表示： f[ i ][ j ] = f[ i -1 ][ j - v[ i ]] + w[ i ] 。也即说明如果我们想让 f[ i ][ j ] 是最大的，那么我们必须保证 f[ i -1 ][ j - v[ i ]] 也是最大的。情况二： f[ i ][ j ] 中没有选择第 i 个物品，那么 f[ i ][ j ] 可以如下表示： f[ i ][ j ] = f[ i -1 ][ j ] 。也即说明如果我们想让 f[ i ][ j ] 是最大的，那么我们必须保证 f[ i -1 ][ j ] 是最大的。

按照上面分析我们发现，对 f[ i ][ j ] 的求解要求前面每一个 f[ x ][ y ] 都是最大的，那么我们可以先求出前面每一个过程中的最大值，进而求解出符合要求的 f[ i ][ j ] 。所以问题可以转换成：对前面每一个状态求最大值，进而得出 f[N][M] 的最大值。可以借助下面代码理解一下。
这是一种从后往前的理解方式，从结果分析出前面每一个状态的特点，再利用这一特点从前往后计算。下面的各种背包问题都可以这样理解
关键在理解 代码很简单 优化也只是对代码的一种变形

核心代码如下：

for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
        	//没有选择第i个物品
            f[i][j]=f[i-1][j];
            //选择了第i个物品
            if(j-v[i]>=0) f[i][j]=max(f[i][j],f[i-1][j-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]);
        }

完全背包问题

问题描述：给定N个物品，给的物品可以无限使用，每个物品都有相应的价值w与体积v，给定体积为M的背包，求背包所能装的最大物品价值。与01背包差别在于：01背包每种物品只能选择一次，而完全背包内的每种物品可以选择无限次。

分析：与01背包差别就在于我们需要讨论每个物品一共选择了几次，虽然物品可以无限使用，但是物品个数还是受到背包体积的限制。

朴素代码

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][j],f[i-1][j-k*v[i]]+w[i]*k);

第一次优化代码

for(int i=1;i<=n;i++)
        for(int j=0;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]);
            }

第二次优化代码

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

#include

using namespace std;
const int N=1010;
int v[N],w[N],f[N];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d",&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]);
            
    //printf("%d",f[n][m]);
    printf("%d",f[m]);
    
    return 0;
}

多重背包问题

问题描述：第 i 种物品最多有 N 件，总共 n 种物品，求最大价值。

分析：把每一物品个数利用2进制方式拆分，最后问题变成了01背包问题。

#include

using namespace std;
const int N=2010,M=130000;
int v[M],w[M];
int f[N];//f[N]个数与背包总体积有关

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int a,b,c;
    int cnt=0;
    for(int i=1;i<=n;i++) 
    {
        scanf("%d%d%d",&a,&b,&c);
        int k=1;
        while(k<=c)
        {
            v[++cnt]=k*a;
            w[cnt]=k*b;
            c-=k;
            k*=2;
        }
        if(c)
        {
            v[++cnt]=c*a;
            w[cnt]=c*b;
        }
    }
    
    for(int i=1;i<=cnt;i++)
        for(int j=m;j>=v[i];j--)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
            
    printf("%d",f[m]);
    
    return 0;
}

分组背包问题

问题描述：N组物品，每组若干个，每组物品只能选择一个

分析：三层循环，枚举第 i 组物品选哪一个

代码

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

#include

using namespace std;
const int N=110;
int v[N][N],w[N][N],f[N],s[N];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&s[i]);
        for(int j=1;j<=s[i];j++) scanf("%d%d",&v[i][j],&w[i][j]);
    }
    
    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)
            for(int k=1;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[m]);
    
    return 0;
}

总结

01背包：f[j]=max(f[j],f[j-v[i]]+w[i]);//j从大到小
完全背包：f[j]=max(f[j],f[j-v[i]]+w[i]);//j从小到大
多重背包：f[j]=max(f[j],f[j-v[i]]+w[i]);//j从大到小
分组背包：f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);//j从大到小

只有完全背包是从小到大