DP之背包问题（01背包+完全背包+分组背包+多重背包+二维费用背包）

时间：2022-04-02 18:39:48

首先是01背包，所有背包问题的基础，看这个博客很棒： 01背包，里面讲的很详细

常规二维写法 
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
using namespace std;
int dp[1005][1005];
int main()
{
    int v[1005];
    int w[1005];

    int t;
    scanf("%d",&t);
    while(t --)
    {
        int n, m;
        scanf("%d%d",&n,&m);
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i ++)
            scanf("%d",&v[i]);
        for(int j = 1; j <= n; j ++)
            scanf("%d",&w[j]);
        for(int i = 1; i <= n; i ++)
            for(int j = 0; j <= m; j ++)
        {
            if(j < w[i])
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]] + v[i]);

        }
        printf("%d\n",dp[n][m]);
    }
    return 0;
}
dp[i][v]是由dp[i-1][v]和dp[i-1][v-c[i]]两个子问题递推而来，能否保证在推dp[i][v]时（也即在第i次主循环中推dp[v]时）能够得到dp[i-1][v]和dp[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推dp[v]，这样才能保证推dp[v]时dp[v-c[i]]保存的是状态dp[i-1][v-c[i]]的值
优化空间后 
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<vector>#include<set>#include<map>#include<queue>#include<cmath>using namespace std;int main(){    int v[1005];    int w[1005];    int dp[1005];    int t;    scanf("%d",&t);    while(t --)    {        memset(dp, 0, sizeof(dp));        int n, V;        scanf("%d%d",&n,&V);        for(int i = 1; i <= n; i ++)            scanf("%d",&w[i]);        for(int i = 1; i <= n; i ++)            scanf("%d",&v[i]);        for(int i = 1; i <= n; i ++)            for(int j = V; j >= v[i]; j --)            {                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);            }            printf("%d\n",dp[V]);    }    return 0;}

然后是完全背包，之前01背包要求逆序，是为了防止物品重复放入，并且可以继承之前的状态，所以完全背包正序即可重复放入

和01背包相似，同一种物品有无数个

完全背包裸题HDU - 1248

#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<vector>#include<set>#include<map>#include<queue>#include<cmath>using namespace std;int main(){    int w[3] = {150, 200, 350};    int v[3] = {150, 200, 350};    int n, t;    int f[10005];    scanf("%d",&t);    while(t --)    {        memset(f, 0, sizeof(f));        scanf("%d",&n);        for(int i = 0; i < 3; i ++)            for(int j = 150; j <= n; j ++)            if(w[i] <= j)            f[j] = max(f[j], f[j - w[i]] + v[i]);        printf("%d\n",n - f[n]);    }    return 0;}
这道题自作聪明把for循环第二层写成了 
for(int j = 150; j <= n; j += 50)

其实n不一定是一个可以被50整除的数，联系完全背包建表过程就可以知道是错误的了，然而这样也不是不可以，只要保证n是可以整除50的数就ok，所以有了下面这个优化，应该又快了不少才对

#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<vector>#include<set>#include<map>#include<queue>#include<cmath>using namespace std;int main(){    int w[3] = {150, 200, 350};    int v[3] = {150, 200, 350};    int n, t;    int f[10005];    scanf("%d",&t);    while(t --)    {        memset(f, 0, sizeof(f));        scanf("%d",&n);        for(int i = 0; i < 3; i ++)            for(int j = 150; j <= n; j += 50)            if(w[i] <= j)            f[j] = max(f[j], f[j - w[i]] + v[i]);        int m = n - (n % 50);        printf("%d\n",n - f[m]);    }    return 0;}

然后是分组背包，分组背包将物品分为了几组，有了新的限制

分组背包使用一维数组的伪代码如下：
for 所有的组k
    for v=V..0
        for 所有的i属于组k
            f[v]=max{f[v],f[v-c[i]]+w[i]}

分组背包裸题HDU - 1712

#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<vector>#include<set>#include<map>#include<queue>#include<cmath>using namespace std;int main(){    int n, m;    int a[105][105];    int dp[105];    while(scanf("%d%d",&n,&m) != EOF&&n&&m)    {        memset(dp, 0, sizeof(dp));        for(int i = 1; i <= n; i ++)            for(int j = 1; j <= m; j ++)            scanf("%d",&a[i][j]);        for(int i = 1; i <= n; i ++)            for(int j = m; j > 0; j --)//倒叙保证每天只能选一种，形似01背包                for(int k = 1; k <= j; k ++)                dp[j] = max(dp[j], dp[j - k] + a[i][k]);        printf("%d\n",dp[m]);    }    return 0;}

为什么倒叙就是01背包而正序就是完全背包呢，因为倒叙无法继承之前的状态，只能选择一个物品，而正序可以在背包容量之内无限添加该物品，关于这点画个图模拟一下就明白了，对于多重背包，就是之前01背包的扩展版本，每个物品的数量都是有限个，要不然不选择该物品，要不然就选择k个，这种问题显然不能用完全背包的思想做，因为完全背包问题中，每一个物品有无限个，而多重背包是有限个，此时我们应该向01背包问题靠拢

for(int i = 1; i <= n; i ++)            for(int j = V; j >= v[i]; j --)

这是01背包核心代码，此时倒叙保证每次只能选择一个物品，如果想要选择多个呢，此时需要在两个for之间加上一个循环，该循环的目的是保证选择该物品的同时，可以延续之前的状态，以达到选择多个物品的目的，必须我要选择两个a物品，用01背包的代码只能完成选择一个，如果再跑一边第二层循环，就能延续之前选择一个a物品的状态，从而实现a物品的第二次添加，所以再跑一边第二层循环，又可以添加一次，即有几个a物品，就跑几次第二层循环，以达到同种物品的多次添加，这样就和01背包很相似了，个人理解描述有限。。

for(int i = 1; i <= m; i ++)            for(int j = 1; j <= num[i]; j ++)                for(int k = n; k >= v[i]; k --)

01背包两层循环之间添加了一个for循环，这就是上面所说的01背包状态延续版本--多重背包

多重背包裸题 HDU - 2191 
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<vector>#include<set>#include<map>#include<queue>#include<cmath>using namespace std;int w[105], v[105], num[105], dp[105];int main(){    int m, n;    int t;    scanf("%d",&t);    while(t --)    {        memset(dp, 0, sizeof(dp));        scanf("%d%d",&n,&m);        for(int i = 1; i <= m; i ++)            scanf("%d%d%d",&v[i],&w[i],&num[i]);        for(int i = 1; i <= m; i ++)            for(int j = 1; j <= num[i]; j ++)                for(int k = n; k >= v[i]; k --)                dp[k] = max(dp[k], dp[k - v[i]] + w[i]);            printf("%d\n",dp[n]);    }    return 0;}

还是这道题，看到大佬写的方法，发现还挺好理解，就是二进制解决问题方面不会证明。。。但确实是快了不少

#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<vector>#include<set>#include<map>#include<queue>#include<cmath>using namespace std;int dp[1005];int c[1005], w[1005], num[1005];int m, n;void zero_pack(int cost, int weigh, int n)//01背包{    for(int i = n; i >= cost; i --)        dp[i] = max(dp[i], dp[i - cost] + weigh);}void complete_pack(int cost, int weigh, int n)//完全背包{    for(int i = cost; i <= n; i ++)        dp[i] = max(dp[i], dp[i - cost] + weigh);}int multi_pack(int c[], int w[], int num[], int n, int m)//多重背包{    memset(dp, 0, sizeof(dp));    for(int i = 1; i <= n; i ++)    {        if(num[i] * c[i] > m)//此种情况视为该物品无限个，用完全背包解决            complete_pack(c[i], w[i], m);        else//否则用01背包解决，用二进制解决问题降低时间复杂度，必定可以凑出结果        {            int k = 1;            while(k < num[i])            {                zero_pack(k*c[i], k*w[i], m);                num[i] -= k;                k <<= 1;            }            zero_pack(num[i]*c[i], num[i]*w[i], m);        }    }    return dp[m];}int main(){    int t;    scanf("%d",&t);    while(t --)    {        scanf("%d%d",&m,&n);        for(int i = 1; i <= n; i ++)            scanf("%d%d%d",&c[i],&w[i],&num[i]);        printf("%d\n",multi_pack(c, w, num, n, m));    }    return 0;}

关于二进制的问题，在网上找了个证明

定理：一个正整数n可以被分解成1,2,4,…,2^(k-1),n-2^k+1（k是满足n-2^k+1>0的最大整数）的形式，且1～n之内的所有整数均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某几个数的和的形式。

证明如下：

（1） 数列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和为n，所以若干元素的和的范围为：[1, n]；

（2）如果正整数t<= 2^k – 1,则t一定能用1,2,4,…,2^(k-1)中某几个数的和表示，这个很容易证明：我们把t的二进制表示写出来，很明显，t可以表示成n=a0*2^0+a1*2^1+…+ak*2^（k-1），其中ak=0或者1，表示t的第ak位二进制数为0或者1.

（3）如果t>=2^k,设s=n-2^k+1，则t-s<=2^k-1，因而t-s可以表示成1,2,4,…,2^(k-1)中某几个数的和的形式，进而t可以表示成1,2,4,…,2^(k-1)，s中某几个数的和（加数中一定含有s）的形式

然后就是二维费用背包，即选择一种物品，需要付出两种费用，在之前的维度上再加一维就行，和之前一样的，倘若是01背包，就倒叙，完全背包就正序，第一层循环不变，仍旧遍历物品种类，第二三层循环可以彼此替换，第二三层决定是01还是完全背包
二维背包 看这个博客很棒

直接挂代码 
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<vector>#include<set>#include<map>#include<queue>#include<cmath>using namespace std;#define inf 0x3f3f3f3fint main(){    int v[105], w[105];    int dp[105][105];    int m, n, k, s;    while(scanf("%d%d%d%d",&n,&m,&k,&s) != EOF)    {        memset(dp, 0, sizeof(dp));        int ans = inf;        int flag = 0;        for(int i = 1; i <= k; i ++)            scanf("%d%d",&v[i],&w[i]);        for(int i = 1; i <= k; i ++)            for(int j = w[i]; j <= m; j ++)                for(int k = 1; k <= s; k ++)                {                    dp[j][k] = max(dp[j][k], dp[j - w[i]][k - 1] + v[i]);                    if(dp[j][k] >= n && j < ans)                    {                        flag = 1;                        ans = j;                    }                }            if(flag) printf("%d\n",m - ans);            else printf("-1\n");    }    return 0;}
标签：

相关文章