Hexo
0%

背包九讲

Posted on In ,
Symbols count in article: 14k Reading time ≈ 13 mins.

背包九讲

背包问题是典型的线性dp问题

01背包

题目大意

有 N 件物品和一个容量为 V 的背包。放入第 i 件物品花费的容积是 c[i] ，得到的价值是 w[i] ，求将哪些物品装入背包可使价值总和最大。

特点：每种物品只有一种

定义状态

dp[i][j]表示前 i 件物品恰放入一个容量为 j 的背包可以获得的最大价值
则状态转移方程为：

dp[i][j] = max(dp[i-1][j] , dp[i-1][j-c[i]] + w[i]])

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxn = 1e5 + 10;
int c[maxn], w[maxn], dp[maxn][maxn];
void solve()
{
    int n, v;
    cin >> n >> v;
    for (int i = 1; i <= n; ++i)
        cin >> c[i];
    for (int i = 1; i <= n; ++i)
        cin >> w[i];
    for (int i = 1; i <= n;++i)
    {
        for (int j = 0; j <= v;++j)
        {
            dp[i][j] = dp[i-1][j];
            if(c[i]<=j){
                dp[i][j] = max(dp[i][j], dp[i - 1][j - c[i]] + w[i]);
                
            }
        }
    }

    cout << dp[n][v] << endl;
}

int main()
{
    // std::ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    solve();
    return 0;
}

此时的时间和空间复杂度均为Θ(V∗N) ,

滚动数组

滚动数组是 dp 中最常用的空间优化技术

使用滚动数组，可以将 dp 的状态维度减少一维

从转移方程可以看出 dp[i][j] = max(dp[i-1][j-v[i]]+w[i],dp[i-1][j]) 只与 dp[i-1]有关，和 dp[i-2],dp[i-3]… 都没有关系，所以我们只需要 dp[i-1] 就够了

交替滚动

定义dp[2][j]，用dp[1][j],dp[0][j]交替滚动

1
2
3
4
5
6
7
8
9
10
for (int i = 1; i <= n; i++)
{
    for (int j = 0; j <= v; j++)
    {
        dp[i & 1][j] = dp[(i & 1) ^ 1][j];
        // 如果当前物品的体积大于当前的容量，显然不能放入
        if (c[i] <= j)
            dp[i & 1][j] = max(dp[i & 1][j], dp[(i & 1) ^ 1][j - c[i]] + w[i]);
    }
}

自我滚动

1
2
3
4
5
6
7
8
9
for (int i = 1; i <= n; i++)
{
    // 逆序！！！
    for (int j = m; j >= 0; j--)
    {
        if (c[i] <= j)
            dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
    }
}

循环 j 的时候记得反过来

初始化问题

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。

有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法，要求恰好装满背包，那么在初始化时除了 dp[0] 为 0，其 它 dp[1...v] 均设为 −∞，这样就可以保证最终得到的 dp[v] 是一种恰好装满背包的 最优解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该 将 dp[0...V]全部设为 0 。

这是为什么呢？可以这样理解：初始化的 F 数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为 −∞ 了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 0 ，所以初始时状态的值也就全部为 0 了。

这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始化进行讲解。

完全背包

题目大意

有N 种物品和一个容量为V 的背包，每种物品都有无限件可用。第 i 种物品的费用是c [ i ] ，价值是w [ i ]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大

思路

这种问题类似于01背包，不同的是每件物品有无限件，而01背包每件物品只有一件。状态方程仍然可以按照01背包时的思路，令dp[i][j]表示前 i 种物品放入一个容量为 j 的背包的最大权值。

1
dp[i][j]=max(dp[i−1][j−k∗c[i]]+k∗w[i])   ∣   0≤k∗c[i]≤j
1
2
3
4
5
6
7
8
9
for (int i = 1; i <= n; i++)//第i件物品
		for (int j = c[i]; j <= V; j++)//背包体积
			for (int k = 0; k * c[i] <= j; k++)//决策数
				dp[i][j] = max(dp[i][j], dp[i - 1][j - k * c[i]] + k * w[i]);
/*
for 物品
    for 体积
        for 决策
*/

注意取 max 时与01背包不同，max 的第一个参数不再是dp[i-1][j]，因为dp[i][j]要在取多件的情况中取最值； 当 k = 0时，dp[i-1][j - k*c[i]] + k*w[i]就相当于dp[i-1][j]，也就是这件物品一件也不取的情况

时间复杂度为Θ(N ∗ Σ(V/c[i]))

多重背包

题目大意

有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 p [ i ] 件可用，每件费用是c [ i ] ，价值是w [ i ] 。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

思路

对于第 i 种物品有 p[i]+1种策略：取0...p[i]件，令dp[i][j]表示前 i 种物品恰放入一个容量为 j 的背包的最大价值，则有状态转移方程

1
dp[i][j]=max(dp[i−1][j−k∗c[i]]+k∗w[i]) ∣     0≤k≤p[i]

暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxn = 1e5 + 10;
int dp[maxn], c[maxn], w[maxn], p[maxn];
int n, m;
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> w[i] >> p[i];

    for (int i = 1; i <= n; ++i)
    {
        for (int j = m; j >= 0; --j)
        {
            for (int k = 1; k * c[i] <= j && k <= p[i]; ++k)
            {
                dp[j] = max(dp[j], dp[j - c[i] * k] + w[i] * k);
            }
        }
    }

    int res = 0;
    for (int i = 1; i <= m; ++i)
        res = max(res, dp[i]);
    cout << res << endl;
}

int main()
{
    // std::ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    solve();
    return 0;
}

时间复杂度: O( 物品数 × 背包的体积 × 选法)

二进制优化法

本质： 将多重背包转化为 01背包问题

思路

暴力法实质上是把多重背包中的每个物品都分成了 p 件，我们可以通过其他分法，可以通过选这些物品，选几个来表示选 s 个的所有可能

这时候就想到了二进制，因为任何实数都可以由二进制数组成。

那么我们就可以把一个物品拆成 $ 2^0 ，2^1 , 2^2 , …… , 2^k , (x-2^{k+1}+1)$ ( k 为最大的 $2^i$ 总和不大于 x 的实数，$log_x$ 个物品

这些物品可以通过组合，组成 0 - x 内的整数（不能漏不能多）

证明

设一个实数 x ， 拆分成 $ 2^0 ，2^1 , 2^2 , …… , 2^k ,c$ ，因 ( k 为最大的 $2^i$ 总和不大于 x 的实数)为 k 是最大的 $2^k$ 不大于 x 的实数，所以可以知道 c < $2^{k+1}$

根据二进制可知 0 到 ($2^{k+1}-1$)都可以用以上的数组成

因为 $2^{k+1}-1+c$为可以凑到的最大值，所以$2^{k+1}-1+c=p => p-(2^{k+1}-1)$

现在已知$0-(2^{k+1}-1)$ 和$c-p$ 两端都可以由以上数拼接起来，现在问题就是，这两段合在一起的时候，中间有无空缺。

如果有空缺的话，$c>2^{k+1}-1$ 即 $c\ge2^{k+1}$

显然与开始得到的 $c<2^{k+1}$相矛盾，可得0-p中的任何一个数都可以拼接起来

时间复杂度：O$( 物品数 \times 背包的体积 \times log 选法) $= O$(N \times V \times logP)$

多重背包问题 ||

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxn = 1e5 + 10;
int n, m;
int c[maxn], w[maxn], p[maxn], dp[maxn];

struct node
{
    int c, w;
} good[maxn];

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> w[i] >> p[i];

    for (int i = 1; i <= n; ++i)
    {
        int cnt = 1;
        // 分成2^k次方的时候
        // 新物品的体积和价值 = 选的个数 *单个的体积和价格
        for (int z = 1; z <= p[i]; z *= 2, ++cnt)
        {
            good[cnt].c = z * c[i];
            good[cnt].w = z * w[i];
            p[i] -= z;
        }

        if (p[i] > 0)//最后一个物品
        {
            good[cnt].c = p[i] * c[i];
            good[cnt++].w = p[i] * w[i];
        }

        //变成了01背包
        for (int j = 1; j < cnt;++j)//遍历选法
        {
            for (int k = m; k >= good[j].c;k--)//遍历体积，由于是滚动一维，所以要逆序遍历
            {
                dp[k]=max(dp[k],dp[k-good[j].c]+good[j].w);
            }
        }
    }

    cout << dp[m] << endl;
}

int main()
{
    // std::ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    solve();
    return 0;
}

单调队列优化法

思路

转移方程dp[i][j] = max(dp[i-1][j], dp[i-1][j-k*c[i]] + k*w[i])

单调队列优化的主要思想就是分组更新，因为w[i]是成倍增加的，dp[i-1][j]只会更新dp[i-1][j+k*w[i]](这里是从前往后看的，所以是+)

对于当前为 w 的体积，我们可以按照余数将它分为 w 组，也就是0… w−1同一个剩余系的数在一组
比如在模 3 意义下，1 , 4 , 7 , 10 是一组，2 , 5 , 8 , 11 是一组，3 , 6 , 9 , 12 是一组
每组的转移是互不影响的，也就是单独转移

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20005;
// pre存储i - 1的时候的值
// q为偏移量为?时候的单调队列
int dp[N], pre[N], q[N], n, m;
int main()
{
    //n为物品的总数，背包容量为m
    scanf("%d%d", &n, &m);
    while (n--)
    {
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);

        //赋值上一层结果
        memcpy(pre, dp, sizeof(dp));
		
        //枚举偏移量(起点)
        for (int i = 0; i < v; i++)
        {
            //建新的单调队列 头>>>尾巴，里面存的是体积
            int head = 0, tail = -1;

            //更新该起点代表的行,k是此时的体积
            for (int k = i; k <= m; k += v)
            {
                //判断窗格是否超过了k,头需要往后滑动
                if (head <= tail && k - q[head] > s * v)
                    head++;

                //赋值
                //pre[q[head]]+(k - q[head]) / v * w)：前i-1个中选，且体积不大于q[head]的最大价值 + 第i个物品选(k - q[head]) / v 个的价值
                if (head <= tail)
                    dp[k] = max(dp[k], pre[q[head]] + (k - q[head]) / v * w);

                //队列中加入k,并且维护队列单调性
                //pre[k]：前i-1个中选，且体积不大于q[head]的最大价值 + 第i个物品选0个
                //pre[q[tail]] + (k - q[tail]) / v * w ：前i-1个中选，且体积不大于q[tail]的最大价值 + 第i个物品选(k - q[tail]) / v个
                while (head <= tail && pre[q[tail]] + (k - q[tail]) / v * w < pre[k])
                    tail--;
                q[++tail] = k;
            }
        }
    }
    printf("%d", dp[m]);
    return 0;
}

演唱会 SOJ1538

混合多种背包问题

题目大意

将前面三个背包混合起来，也就是说，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）

思路

当前物品的选法，和相应的更新值，和之前的物品类型无关。所以每次判断当前物品的类型，选择对应的转移方程来进行转移就可以了。

二维费用背包问题

题目大意

二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值

P1507 NASA的食物计划

航天飞机的体积有限，当然如果载过重的物品，燃料会浪费很多钱，每件食品都有各自的体积、质量以及所含卡路里。在告诉你体积和质量的最大值的情况下，请输出能达到的食品方案所含卡路里的最大值，当然每个食品只能使用一次。

思路

状态定义：

现在不仅仅是对体积有限制，还对质量有限制，因此我们在选择一个物品时还应该在意当前的质量，所以需要在01背包的基础上再加一个维度

定义dp[i][j][k]为遍历到第 i 个物品，当前体积不超过 j ，质量不超过 k 获得的最大卡路里值

转移方程

dp[i][j][k]=max(dp[i−1][j][k],dp[i−1][j−c[i]][k−g[i]]+w[i])

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
const int N = 55, M = 4e2 + 5;
int h1[N], t1[N], k1[N];
int f[N][M][M];
int main()
{
    int h, t, n;
    scanf("%d%d%d", &h, &t, &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d", &h1[i], &t1[i], &k1[i]);

    for (int i = 1; i <= n; i++)
    {
        f[i][0][0] = f[i - 1][0][0];
        for (int j = 1; j <= h; j++)
            for (int k = 1; k <= t; k++)
            {
                f[i][j][k] = f[i - 1][j][k];
                if (h1[i] <= j && t1[i] <= k)
                {
                    f[i][j][k] = max(f[i][j][k], f[i - 1][j - h1[i]][k - t1[i]] + k1[i]);
                }
            }
    }
    printf("%d\n", f[n][h][t]);

    return 0;
}

物品总个数的限制

有时,”二维费用” 的条件是以这样一种隐含的方式给出的：最多只能取 U 件物品。这事实上相等于每件物品多了一种 “件数” 的费用，每个物品的件数费用均为 1 ，可以付出的最大件数费用为 U

分组背包

题目大意

有 N 件物品和一个容量为 V 的背包。第i ii件物品的费用是 c [ i ] ，价值是 w [ i ] 。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

思路

将同一组的物品整合起来，称为一个大物品，那么问题就变成了若干个大物品中，每个可以选择其中的一个物品，求总费用不超过限制的价值最大值是多少？

其实可以发现，这个非常的类似多重背包。

定义f[k][j]为遍历到第 k 个大物品，当前体积不超过 j 的价值最大值

f[k][j] = max(f[k-1][j] , f[k-1][j-c[i]]+w[i]) 物品 i $\subseteq $组别 k

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1005;
int dp[N][N], q[N];
struct node
{
    int wei, val;
    node(int a, int b)
    {
        wei = a, val = b;
    }
};
vector<node> ve[N];

int main()
{
    int n, m;
    scanf("%d%d", &m, &n);
    int we = 0;
    for (int i = 1; i <= n; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        ve[c].push_back(node(a, b));
        we = max(we, c);
    }
    for (int i = 0; i <= we; i++)
        for (int j = 0; j <= m; j++)
            dp[i][j] = -1e9;

    dp[0][0] = 0;
    // 遍历物品
    for (int i = 1; i <= we; i++)
    {
        // 遍历体积
        for (int j = 0; j <= m; j++)
        {
            // 遍历决策
            dp[i][j] = dp[i - 1][j];
            for (int k = 0; k < ve[i].size(); k++)
            {
                if (ve[i][k].wei <= j)
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - ve[i][k].wei] + ve[i][k].val);
            }
        }
    }

    int res = 0;
    for (int i = 0; i <= m; i++)
        res = max(res, dp[we][i]);
    printf("%d\n", res);
    return 0;
}

有依赖的背包问题

这种背包问题的物品间存在某种“依赖”的关系。也就是说，i 依赖于 j ，表示若选物品 i ，则必须选物品 j 。

比如：

要求你加入集训队试训前，一定要刷完专题

题目大意

给出每个物品的价格和重要度和是否是主件或者说是谁的附件，求最后选出的每件物品的价格与重要度乘积和的最大值，每个附件不再有附件。

P1064 [NOIP2006 提高组] 金明的预算方案

主件 附 件
电脑 打印机，扫描仪
书柜 图书
书桌 台灯，文具
工作椅 无

一个主件和它的附件集合是几乎对于分组背包中的一个物品组。

每个选择了主件又选择了若干附件的策略，对应这个物品组的中的一个物品。

思路

我们可以将每个主件选附件的问题看成一个01背包问题，这样当我们知道给一个主件分配多少价钱的时候，就可以知道此时这个主件及其附件在对应的价钱可以获得的最大价值

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 4e3 + 5, M = 65;
vector<int> ve[M];
int wei[M], imp[M];//价格和重要度
int n, m;
int dp[M][N];
int main()
{
    scanf("%d%d", &m, &n);
    m /= 10;
    for (int i = 1; i <= n; i++)
    {
        int c;
        scanf("%d%d%d", &wei[i], &imp[i], &c);
        wei[i] /= 10;
        ve[c].push_back(i);
    }

    // 先处理给出每个主件分配不同空间时对应获得的最大价值
    //  遍历各主件
    for (int u = 1; u <= n; u++)
    {
        // 01背包问题----(这里滚动了变成了一个维数组)
        // dp[u][j] 表示第 u 个背包，分配 j 体积 可以获得的最大价值
        //  遍历附件（物品数量)
        for (int j = 0; j < ve[u].size(); j++)
        {
            int to = ve[u][j];
            for (int k = m; k >= wei[to]; k--)
            {
                dp[u][k] = max(dp[u][k], dp[u][k - wei[to]] + imp[to] * wei[to] * 10);
            }
        }
    }

    // 整合
    // 遍历主件
    for (int i = 0; i < ve[0].size(); i++)
    {
        int to = ve[0][i];
        for (int j = m; j >= wei[to]; j--)//逆序！
        {
            // 遍历给当前主件的附件分配的空间
            for (int k = j - wei[to]; k >= 0; k--)
            {
                dp[0][j] = max(dp[0][j], dp[to][k] + imp[to] * wei[to] * 10 + dp[0][j - k - wei[to]]);
            }
        }
    }
    printf("%d\n", dp[0][m]);

    return 0;
}

较一般的题目

依赖关系以图论中的 “森林” 形式给出，也就是说主件的附件依旧可以有自己的附件集合。

刚刚那道题可以直接那么做，主要是因为附件没有附件，如果还有附件的话，就需要继续先计算出附件在面对各价格时可获得的最大值才可以。

这种背包就是 树形背包 （树形dp的一种），它的特点是每个父节点都需要对它的各个儿子的属性进行一次 dp 来求得自己相关的属性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 4e3 + 5, M = 65;
vector<int> ve[M];
int wei[M], imp[M];
int n, m;
int dp[M][N];
void dfs(int u)
{
    //枚举物品
    for (int i = 0; i < ve[u].size(); i++)
    {
        int to = ve[u][i];
        dfs(to);
        for (int j = m; j >= 0; j--)
        {
            //枚举分给当前物品的体积
            for (int k = j; k >= 0; k--)
            {
                if (k - wei[to] >= 0)
                    dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[to][k - wei[to]] + imp[to] * wei[to] * 10);
                else
                    break;
            }
        }
    }
}

int main()
{
    scanf("%d%d", &m, &n);
    m /= 10;
    for (int i = 1; i <= n; i++)
    {
        int c;
        scanf("%d%d%d", &wei[i], &imp[i], &c);
        wei[i] /= 10;
        ve[c].push_back(i);
    }
    dfs(0);
    int res = 0;
    res = dp[0][m];
    printf("%d\n", res);
    return 0;
}

背包问题的变化

输出方案

一般而言，背包问题是要求一个最优值，如果要求输出这个最优值的方案，可以参照一般动态规划问题输出方案的方法: 记录下每个状态的最优质是由状态转移方程的哪一项推出来的。然后就可以根据这个状态继续往前推导。

题目大意

01背包问题，但是要求输出 字典序最小的方案数 。

思路

求具体方案其实就是判断每个物品是否被选，求方案其实就是从dp[n][m]倒推出来每一个 i 是否选择

需要根据转移方程来判断是否选择第 i 个物品，所以不能滚动。

这里要求字典序最小，所以采用贪心的策略

然后对于每一个物品来说可能有三种情况

  • 只能选 —— 必选
  • 只能不选 —— 必不选
  • 可选可不选 —— 一定要选

显然求字典序最小的时候，我们需要优先考虑编号小的物品，但是找方案的时候，又是从 dp[n][m] 开始回推的，所以我们在求解 01 背包的时候，从后往前推，就可以从 dp[1][m]始往前推了，这样的话，就和求字典序最小的顺序一致了。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxn = 1e3 + 10;
int dp[maxn][maxn], n, m, w[maxn], c[maxn];
void solve(){
    cin >> n >> m;
    for (int i = 1; i <= n;++i)
        cin >> c[i] >> w[i];

    for (int i = n; i >= 1;--i)//逆序，使得编号小的可以从编号大的推算而出
    {
        for (int j = 0; j <= m;++j)
        {
            dp[i][j] = dp[i + 1][j];

            if(j>=c[i])
                dp[i][j] = max(dp[i][j], dp[i + 1][j - c[i]] + w[i]);
        }
    }

    int j = m;
    for (int i = 1; i <= n;++i)
    {
        if(j-c[i]>=0&&dp[i][j]==dp[i+1][j-c[i]]+w[i])//分治
        {
            cout << i << endl;
            j -= c[i];
        }
    }
}

int main(){
//std::ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
solve();
return 0;
}

求第K优解

题目大意

01背包问题，但是需要输出的是可以获得的第 K 大价值。

思路

我们需要得到的是第 K 大价值，所以当我们得到一个当前为 K+1 大的价值时，就直接舍去。因为它一定不是第 K 大价值，然后我们又需要得到目前得到的 K 个价值具体是多少，所以我们在原来01背包的基础上再加一维

定义dp[i][j][k]: 遍历到第 i 个物品，且体积不超过 j 可得到的第 k 大价值

为了方便，滚动数组优化掉第一个维度，即状态变成dp[i][j]：体积不超过 i 时可以得到的第 j 大价值是多少

01背包的状态转移方程:dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]]+w[i])

划分了当前选和不选，显然这里的选择会影响到当前状态的 k 个最大值

所以我们取出这两种选法对应的 2*k 个数，排序成新的 k 个最大数

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <algorithm>
using namespace std;
int dp[1005][35], wei[105], val[105];
int main()
{
        int n, v, k;
        scanf("%d%d%d", &n, &v, &k);
        for (int i = 1; i <= n; i++)
            scanf("%d", &val[i]);
        for (int i = 1; i <= n; i++)
            scanf("%d", &wei[i]);

        for (int i = 1; i <= v; i++)
            for (int j = 1; j <= k; j++)
                dp[i][j] = 0;

        for (int i = 1; i <= n; i++)
        {
            for (int j = v; j >= wei[i]; j--)
            {
                //a数组记录的是不选第 i 个物品的 k 个最大价值
                //b数组记录的是选第 i 个物品的 k 个最大价值
                int a[35] = {0}, b[35] = {0};
                for (int l = 1; l <= k; l++)
                {
                    a[l] = dp[j][l];
                    b[l] = dp[j - wei[i]][l] + val[i];
                }
                a[k + 1] = b[k + 1] = -1;

                int ai = 1, bi = 1;
                for (int l = 1; l <= k && (a[ai] != -1 || b[bi] != -1); l++)
                {
                    if (a[ai] > b[bi])
                        dp[j][l] = a[ai++];
                    else
                        dp[j][l] = b[bi++];
                    //相同的数算同一个
                    if (dp[j][l] == dp[j][l - 1])
                        l--;
                }
            }
        }
        printf("%d\n", dp[v][k]);
    return 0;
}
序号 题号 标题 题目类型 难度评级 题解
1 HDU 2602 Bone collector 01背包 ⭐
2 P1060 开心的金明 01背包 ⭐
3 P2871 Charm Bracelet S 01背包 ⭐
4 P1156 垃圾陷阱 01背包 ⭐⭐
5 POJ 1276 Cash Machine 多重背包 ⭐
6 POJ 1014 Dividing 多重背包 ⭐
7 P5365 英雄联盟 多重背包 ⭐⭐
8 P1776 宝物筛选 多重背包 ⭐⭐
9 P1853 投资的最大效益 多重背包 ⭐⭐
10 P1782 旅行商的背包 混合背包 ⭐⭐
11 P2851 The Fewest Coins G 混合背包 ⭐⭐⭐
12 P1833 樱花 混合背包 ⭐⭐
13 P1507 NASA的食物计划 二维费用背包 ⭐
14 HDU 1712 ACboy needs your help 分组背包 ⭐
15 P1757 通天之分组背包 分组背包 ⭐
16 P1064 金明的预算方案 有依赖背包 ⭐⭐
17 P3961 黄金矿工 有依赖背包 ⭐⭐⭐
18 POJ 1015 Jury Compromise 01背包+输出具体方案 ⭐⭐⭐
19 HDU 2639 Bone Collector || 求第 k 优解 ⭐⭐
20 P1858 多人背包 求第 k 优解 ⭐⭐