算法竞赛进阶指南 0x52 背包

2022/7/25 1:55:22

本文主要是介绍算法竞赛进阶指南 0x52 背包,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

背包问题是线性背包中的一类重要问题。

0/1背包

模型:
给定N个物品,每一个物品具有两种属性,一个是体积 \(v_i\) ,另一个是容积 \(w_i\) 。
有一个容积为M的背包,求一种方案,使得选择的物品的体积不超过背包体积的情况下,使得获得的总价值最大。

0/1背包的时间复杂度是\(O(n*m)\)。

空间复杂度随着写法的不同而不同。

方法一:按照定义写

#include <bits/stdc++.h>
using namespace std;
int n, m;//n表示的是商品的数目,m表示的是背包的容积。
int f[100][100];
int v[100];//第i个物品的体积
int w[100];//第i个物品的价值
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", v+i);
    for(int i = 1; i <= n; i++) scanf("%d", w+i);
    memset(f, 0xcf, sizeof(f));
    //求最优化问题时,把整体全部赋值为无穷大,这样可以防止不合法的情况对最终的判断造成干扰
    f[0][0] = 0;
    //只需要赋值这一个就好,随着DP进行,f[i][0]全部都会是0。
    //虽然f[0][i](i > 0)还是正无穷大,但是对于答案不会造成影响。
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= m; j++) f[i][j] = f[i-1][j];//要注意从0开始进行。
        for(int j = v[i]; j <= m; j++) 
            f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i]);
    }

    return 0;
}

方法二:采用滚动数组来进行求解。

原理:观察到更新时所使用到的信息仅仅与上一行有关系,与其他行并没有关系。

所以可以采用2*m的滚动数组。

#include <bits/stdc++.h>
using namespace std;
int n, m;//n表示的是商品的数目,m表示的是背包的容积。
int f[2][100];
int v[100];//第i个物品的体积
int w[100];//第i个物品的价值
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", v+i);
    for(int i = 1; i <= n; i++) scanf("%d", w+i);
    memset(f, 0xcf, sizeof(f));
    //求最优化问题时,把整体全部赋值为无穷大,这样可以防止不合法的情况对最终的判断造成干扰
    f[0][0] = 0;
    //只需要赋值这一个就好,随着DP进行,f[i][0]全部都会是0。
    //虽然f[0][i](i > 0)还是正无穷大,但是对于答案不会造成影响。
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= m; j++) f[i&1][j] = f[(i-1)&1][j];//要注意从0开始进行。
        for(int j = v[i]; j <= m; j++) 
            f[i&1][j] = max(f[i&1][j], f[(i-1)&1][j-v[i]]+w[i]);
    }

    return 0;
}

总结:滚动数组可以使用位运算&来进行,这样既可以达到f数组的维护,还便于计数。

方法三:采用一维数组进行维护

条件:可以使用滚动数组进行实现,并且按照一定的扫描顺序,更新过的值不会参与到其他值的计算中。

#include <bits/stdc++.h>
using namespace std;
int n, m;//n表示的是商品的数目,m表示的是背包的容积。
int f[100];
int v[100];//第i个物品的体积
int w[100];//第i个物品的价值
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", v+i);
    for(int i = 1; i <= n; i++) scanf("%d", w+i);
    memset(f, 0xcf, sizeof(f));
    //求最优化问题时,把整体全部赋值为无穷大,这样可以防止不合法的情况对最终的判断造成干扰
    f[0] = 0;
    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]);
    }

    return 0;
}

AcWing278. 数字组合

给定 N 个正整数 A1,A2,…,A**N,从中选出若干个数,使它们的和为 M,求有多少种选择方案。

输入格式

第一行包含两个整数 NM

第二行包含 N 个整数,表示 A1,A2,…,A N

输出格式

包含一个整数,表示可选方案数。

数据范围

1≤N≤100,
1≤M≤10000,
1≤A i≤1000,
答案保证在 int 范围内。

输入样例:

4 4
1 1 2 2

输出样例:

3

这道题目也可以看做是0/1背包的变种。
(n个数字选择一些)

代码实现

#include <bits/stdc++.h>
using namespace std;
int f[10020];
int a[102];//存储每一个数字的大小
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    f[0] = 1;
    for(int i = 1; i <= n; i++) scanf("%d", a+i);
    for(int i = 1; i <= n; i++)
    {
        for(int j = m; j >= a[i]; j--)
            f[j] += f[j-a[i]];
    }
    printf("%d", f[m]);
    return 0;
}

细节的考虑

现在从最一开始进行考虑:

对于f[105][10020],全部初始化为0;

f[0][0]初始化为1;

image

然后优化即可。

完全背包

模型:
给定N种物品,每一种物品具有两种属性,一个是体积 \(v_i\) ,另一个是容积 \(w_i\) 。
有一个容积为M的背包,求一种方案,使得选择的物品的体积不超过背包体积的情况下,使得获得的总价值最大。
与0/1背包不同的最大之处在于对于一种物品,可以选择无数次。

精髓:

对于完全背包,由于一个物品可以选择许多次,所以有以下方程

\[f[i][j]=max(f[i][j], f[i-1][j])//表示不选择第i个物品\\ f[i][j]=max(f[i][j], f[i-1][j-kv_i]+kw_i)(k取值从1开始,让j\ge kv_i) \]

但是第二步骤显得过于冗杂,所以不妨优化为

\[f[i][j]=max(f[i][j], f[i][j-v_i]+w_i) \]

上面这一个蕴含玄机:这种情况一定选择了一种以上,至于到底是多少,并不关心,反正是选择多次这一个物品,使得总价值最大。

优化:

和0/1背包一致,使用一维数组,只不过这一次是要从左向右。

模板

int a[100];//体积
int f[100];
int w[100];//价值
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", a+i);
    for(int i = 1; i <= n; i++) scanf("%d", w+i);
    memset(f, 0xcf, sizeof(f));
    f[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = a[i]; j <= m; j++)
            f[j] = max(f[j], f[j-a[i]]+w[i]);
    }
    return 0;
}

AcWing279. 自然数拆分

给定一个自然数 N,要求把 N 拆分成若干个正整数相加的形式,参与加法运算的数可以重复。

注意:

  • 拆分方案不考虑顺序;
  • 至少拆分成 2 个数的和。

求拆分的方案数 mod2147483648 的结果。

输入格式

一个自然数 N

输出格式

输入一个整数,表示结果。

数据范围

1≤N≤4000

输入样例:

7

输出样例:

14

这一种题目看起来简直不像是背包问题。。。

但是可以进行归纳:

有体积为1~n的物品以及体积为n的背包,每一个物品可以放入多次,求使得背包装满的方案数。

#include <bits/stdc++.h>
using namespace std;
#define N 4010
typedef long long ll;
const ll mod = 2147483648;
ll f[N];
int n;
int main()
{
    scanf("%d", &n);
    f[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = i; j <= n; j++)
            f[j] = (f[j-i]+f[j])%mod;
    }
    printf("%d", f[n]-1);//因为需要拆分成为两个数字,所以必须要减去一
    return 0;
}

AcWing280. 陪审团

在一个遥远的国家,一名嫌疑犯是否有罪需要由陪审团来决定。陪审团是由法官从公民中挑选的。

法官先随机挑选 N 个人(编号 1,2…,N)作为陪审团的候选人,然后再从这 N 个人中按照下列方法选出 M 人组成陪审团。

首先,参与诉讼的控方和辩方会给所有候选人打分,分值在 0 到 20 之间。第 i 个人的得分分别记为 p[i] 和 d[i]。为了公平起见,法官选出的 M 个人必须满足:辩方总分 D 和控方总分 P 的差的绝对值 |DP| 最小。如果选择方法不唯一,那么再从中选择辨控双方总分之和 D+P 最大的方案。求最终的陪审团获得的辩方总分 D、控方总分 P,以及陪审团人选的编号。

注意:若陪审团的人选方案不唯一,则任意输出一组合法方案即可。

输入格式

输入包含多组测试数据。每组测试数据第一行包含两个整数 NM。接下来 N 行,每行包含两个整数 p[i] 和 d[i]。每组测试数据之间隔一个空行。当输入数据 N=0,M=0 时,表示结束输入,该数据无需处理。

输出格式

对于每组数据,第一行输出 Jury #CC 为数据编号,从 1 开始。

第二行输出 Best jury has value P for prosecution and value D for defence:P 为控方总分,D 为辩方总分。

第三行输出按升序排列的陪审人选编号,每个编号前输出一个空格。

每组数据输出完后,输出一个空行。

数据范围

1≤N≤200,
1≤M≤20
0≤p[i],d[i]≤20

输入样例:

4 2
1 2
2 3
4 1
6 2
0 0

输出样例:

Jury #1
Best jury has value 6 for prosecution and value 4 for defence:
 2 3
 

算是比较难的一道题目。

如果使用动态规划,会发现有四个维度

  1. 在N个人中,已经处理了的人的数目。
  2. 已经选择的人的数目。
  3. 所有辩方与控方的差。
  4. 辩方以及控方法和。

(要满足差的绝对值最小的情况下,和最大)

闫氏DP分析法:

状态表示
f[i][j][k],i表示考虑过人的数目,j表示选择的人的数目,k表示差值
把差值相同的视为一个类,集合的属性就是和最大的方案。
找差最小的时候可以枚举所有差的可能性。

状态转移
类似0/1背包:

  • 如果不选择第i个人,那么就会有f[i][j][k] = max(f[i][j][k], f[i-1][j][k]).
  • 如果选择第i个人,那么就会有f[i][j][k] = max(f[i][j][k], f[i-1][j-1][ k- ( p[i]-d[i] ) ])

因为最后需要的是方案数,所以需要进行回溯

可以使用结构体存起来,也可以使用到往回推的方式。

在这里,由于有两个维度,所以不太好压缩,
同时由于需要到着往回推算,所以也不能够压缩。

感觉这道题目就算不需要求方案数,我也要进行一下回溯。

#include <bits/stdc++.h>
using namespace std;
#define N 205
#define M 25
#define P 805
const int base = 400;//使用base把负的数字映射到正的数字上
int p[N], d[N];
int f[N][M][P];
int ans[M];
int main()
{
    int T = 0;
    int n, m;
    while(scanf("%d%d", &n, &m), n || m)
    {
        for(int i = 1; i <= n; i++) 
        {
            scanf("%d%d", p+i, d+i);
        }
        memset(f, 0xcf, sizeof(f));
        f[0][0][base] = 0;
        //初始值应该是只有这么一种合法情况。
        for(int i = 1; i <= n; i++)
            for(int j = 0; j <= m; j++)// ***********从0开始(这样到最后会有f[i][0][base]全部是0)
            //试想:有f[3][1][2+base](假设p[3]+d[3]==2),那么如果是选择了第三个人,那么退回去f[2][0][base] == 0,合法,
            //而对于其他的f[3][1][xx],退回去是不合法的情况。
                for(int k = 0; k < P; k++)
                {
                    f[i][j][k] = f[i-1][j][k];
                    int tmp = k-(p[i] - d[i]);
                    //if(tmp < 0 || tmp >= P) continue;//这一句话其实可以省略(因为根据题设条件应该是不会超过范围)
                    if(j < 1) continue;//这一句话不可以省略。使得j==0的时候不参与第二种情况的更新。
                    f[i][j][k] = max(f[i][j][k], f[i-1][j-1][tmp]+p[i]+d[i]);//注意p[i]+d[i]这里是加
                }
        int u = 0;
        while(f[n][m][base+u] < 0 && f[n][m][base-u] < 0) u++;//小于0,可以等于0,如果评审团给所有人的打分全部是0
        if(f[n][m][base+u] > f[n][m][base-u]) u = base+u;
        else u = base-u;

        int cnt = 0;
        {
            int i = n, j = m;
            while(j)
            {
                if(f[i][j][u] == f[i-1][j][u])
                {
                    i--;
                }
                else
                {
                    ans[++cnt] = i;
                    u = u-(p[i] - d[i]);
                    i--;
                    j--;
                }
            }
        }
        int sp = 0, sd = 0;
        for(int i = 1; i <= cnt; i++) sp += p[ans[i]], sd += d[ans[i]];
        printf("Jury #%d\n", ++T);
        printf("Best jury has value %d for prosecution and value %d for defence:\n", sp, sd);
        for(int i = cnt; i >= 1; i--) printf(" %d", ans[i]);
        puts("\n");

    }
    return 0;
}

多重背包

多重背包是介于0/1背包以及完全背包之间的一个问题

模型:
给定N种物品,每一种物品具有三种属性,一个是体积 \(v_i\) ,一个是容积 \(w_i\) ,还有一个是数量\(num_i\)。
有一个容积为M的背包,求一种方案,使得选择的物品的体积不超过背包体积的情况下,使得获得的总价值最大。

这里有三种拆分方法

  1. f[i][j] = max(f[i-1][j], f[i-1][j-v]+w, f[i-1][j-2v]+2w, ....f[i-1][j-sv]+sw)
  2. 直接拆分。
  3. 二进制拆分。
  4. 使用优先队列进行优化。

AcWing4. 多重背包问题 I

N 种物品和一个容量是 V 的背包。第 i 种物品最多有 s**i 件,每件体积是 v**i,价值是 w**i

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

输入格式

第一行两个整数,NV,用空格隔开,分别表示物品种数和背包容积。接下来有 N 行,每行三个整数 v**i,w**i,s**i,用空格隔开,分别表示第 i 种物品的体积、价值和数量。

输出格式

输出一个整数,表示最大价值。

数据范围

0<N,V≤100

0<v**i,w**i,s**i≤100

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例:

10

这一道题目数据量很水,所以使用直接拆分(时间复杂度过于高!!!)

#include <bits/stdc++.h>
using namespace std;
#define N 120
int v[N], w[N], s[N];
int f[N];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    //memset(f, 0xcf, sizeof(f));
    //f[0] = 0;
    //0/1背包貌似不应该初始化。。。
    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 <= s[i]; j++)//默认有这么多。
            for(int k = m; k >= v[i]; k--)
            {
                f[k] = max(f[k], f[k-v[i]]+w[i]);
            }
    printf("%d", f[m]);
    return 0;
}

AcWing5. 多重背包问题 II

N 种物品和一个容量是 V 的背包。

i 种物品最多有 s**i 件,每件体积是 v**i,价值是 w**i

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

输入格式

第一行两个整数,NV,用空格隔开,分别表示物品种数和背包容积。

接下来有 N 行,每行三个整数 v**i,w**i,s**i,用空格隔开,分别表示第 i 种物品的体积、价值和数量。

输出格式

输出一个整数,表示最大价值。

数据范围

0<N≤1000
0<V≤2000
0<v i,w i,s i≤2000

提示:

本题考查多重背包的二进制优化方法。

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例:

10

这是二进制拆分的节奏

二进制拆分太奇妙了!!!!!

如果是直接拆分,相当于是把个数拆分成一堆的1,根据这些1,可以组成任意一种数目。

但是显然没有必要。如果使用二进制拆分,那么可以根据已有的“虚拟的”物品的选择与否,组合成任意数目的等价于选择了\(k(k\in[1, num[i]])\)的这一个物品。

注意:所给定的二进制数字仅且仅仅可以表示出0~num[i]的数字

#include <bits/stdc++.h>
using namespace std;
#define N 2020
int s[N], w[N], v[N];
struct QWER{
    int w, v;
};
vector<QWER>vec;
int f[N];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d%d%d", w+i, v+i, s+i);
    for(int i = 1; i <= n; i++)
    {
        int t = s[i];
        for(int k = 1; k <= t; k *= 2)
        {
            t -= k;
            vec.push_back({w[i]*k, v[i]*k});
        }
        if(t > 0) vec.push_back({w[i]*t, v[i]*t});
    }
    for(int i = 0; i < vec.size(); i++)
    {
        int val = vec[i].v;
        int wei = vec[i].w;
        for(int j = m; j >= wei; j--)
        {
            f[j] = max(f[j], f[j-wei]+val);
        }
        //printf("%d %d \n", val, wei);
    }
    
    printf("%d", f[m]);
    return 0;
}

AcWing281. 硬币

给定 N 种硬币,其中第 i 种硬币的面值为 A i,共有 C i 个。

从中选出若干个硬币,把面值相加,若结果为 S,则称“面值 S 能被拼成”。求 1∼M 之间能被拼成的面值有多少个。

输入格式

输入包含多组测试用例。每组测试用例第一行包含两个整数 NM

第二行包含 2N 个整数,分别表示 A1,A2,…,A**NC1,C2,…,C**N

当输入用例 N=0,M=0 时,表示输入终止,且该用例无需处理。

输出格式

每组用例输出一个结果,每个结果占一行。

数据范围

\(1≤N≤100\),
\(1≤M≤10^5\),
\(1≤A_i≤10^5\),
\(1≤C_i≤1000\)

输入用例:

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0

输出用例:

8
4

虽然是POJ的"男人八题",但是还是可以做的。

对于这里,最朴素的做法int f[][]
其中,f[i][j]表示:在考虑了前i个物品,体积恰好是j的所选物品的集合。
属性是:这个集合内是否有元素(是一个bool值)

对于第 i 个物品,有状态转移方程
f[i][j] = f[i-1][j] || f[i-1][j-v] || f[i-1][j-2v]...

这一个是最朴素的转移方程,由于这一道题会卡常,所以要通过最朴素的方式寻找常数更加少的方案。

在寻找是否有一个1的时候,可以采用数组g保留与该位置最近的1距离该位置是多远。
如果距离大于s,那么不可以
如果距离小于等于s,那么可以

AcWing9. 分组背包问题

N 组物品和一个容量是 V 的背包。

每组物品有若干个,同一组内的物品最多只能选一个。 每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。输出最大价值。

输入格式

第一行有两个整数 NV,用空格隔开,分别表示物品组数和背包容量。接下来有 N 组数据:

  • 每组数据第一行有一个整数 S i,表示第 i 个物品组的物品数量;
  • 每组数据接下来有 S i 行,每行有两个整数 v i j,w i j,用空格隔开,分别表示第 i 个物品组的第 j个物品的体积和价值;

输出格式

输出一个整数,表示最大价值。

数据范围

0<N,V≤100
0<S i≤100
0<v i j,w** i j≤100

输入样例

3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例:

8

其实也没有什么好的优化方法,直接\(N^3\)暴力进行。

#include <bits/stdc++.h>
using namespace std;
#define N 105
int v[N], w[N];
int f[N];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        int c;
        scanf("%d", &c);
        for(int j = 1; j <= c; j++) scanf("%d%d", v+j, w+j);
        for(int j = m; j >= 0; j--)
        {
            for(int k = 1; k <= c; k++)
                if(v[k] <= j)
                    f[j] = max(f[j], f[j-v[k]]+w[k]);
        }
    }
    printf("%d", f[m]);
    return 0;
}


这篇关于算法竞赛进阶指南 0x52 背包的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程