专题 | 背包问题

· · 个人记录

目录

补充资料

https://www.cnblogs.com/ailanxier/p/13370753.html

01背包

简介

01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2至Wn，与之相对应的价值为P1,P2至Pn。01背包是背包问题中最简单的问题。01背包的约束条件是给定几种物品，每种物品有且只有一个，并且有权值和体积两个属性。在01背包问题中，因为每种物品只有一个，对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中，则不需要处理。如果选择将其放入背包中，由于不清楚之前放入的物品占据了多大的空间，需要枚举将这个物品放入背包后可能占据背包空间的所有情况。

思想

DP思想

记一个数组f[i][j]，表示当前选到第i件物品，背包剩余空间为j

决策

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

f[i][j]取以下情况中的最大值

w[i]表示i的占用空间 c[i]表示i的价值 请思考。

循环

i++{j++}

例题

一个旅行者有一个最多能装 M 公斤的背包，现在有 n 件物品，它们的重量分别是W1，W2，...,Wn ,它们的价值分别为C1,C2,...,Cn ，求旅行者能获得最大总价值。

解决

#include <bits/stdc++.h>
using namespace std;
int m, n, w[205], c[205], f[205][205];

int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> c[i];
    for (int i = 1; i <= n; i++) {
        for (int j = m; j > 0; j--) {
            if (w[i] <= j)
                f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + c[i]);
            else
                f[i][j] = f[i - 1][j];
        }
    }

    cout << f[n][m];
    return 0;
}

完全背包

简介

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

基本思路

这个问题非常类似于01背包问题，所不同的是每种物品有无限件，也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……取[V/c]件等很多种。如果仍然按照解01背包时的思路，令f[v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：

f[j]=max{f[j],f[j-k*c]+k*w}（0<=k*c<=v）

这跟01背包问题一样有O(N*V)个状态需要求解，但求解每个状态f[v]的时间是O(V/c)，总的复杂度是超过O(VN)的。 将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明01背包问题的状态转移方程可以推及其它类型的背包问题。但是由于复杂度太高，我们还是试图改进这个复杂度。

简单有效优化

完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j]，则将物品j去掉，不用考虑。这个优化的正确性显然：任何情况下都可将价值小费用高得j换成物美价廉的i，得到至少不会更差的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。这个优化可以简单的O(N^2)地实现，一般都可以承受。 另外，针对背包问题而言，比较不错的一种方法是：首先将费用大于V的物品去掉，然后使用类似计数排序的做法，计算出费用相同的物品中价值最高的是哪个，可以O(V+N)地完成这个优化。这个不太重要的过程就不给出伪代码了，希望你能独立思考写出伪代码或程序。 既然01背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是，考虑到第i种物品最多选V/c件，于是可以把第i种物品转化为V/c件费用为c[I]及价值w[I]的物品，然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将完全背包问题转化为01背包问题的思路：将一种物品拆成多件物品。 更高效的转化方法是：把第i种物品拆成费用为c*2^k、价值为w*2^k的若干件物品，其中k满足0<=k<=log_2(V/c)+1。这是二进制的思想，因为不管最优策略选几件第i种物品，总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log_2(V/c))件物品，是一个很大的改进。

最优解法

for i=1..N
    for j=c..V
        f[j]=max{f[j],f[j-c]+w}

你会发现，这个伪代码与01背包的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢？ 首先想想为什么01背包中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[v]是由状态f[v-c]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个没有已经选入第i件物品的子结果f[v-c]。 而当前完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[v-c]，所以就可以并且必须采用v=0..V的顺序循环。这就是这个简单的程序为何成立的道理。 这个算法也可以以另外的思路得出。例如，基本思路中的状态转移方程可以等价地变形成这种形式：

f[j]=max{f[j],f[j-c]+w}

将这个方程用一维数组实现，便得到了上面的伪代码。 最后抽象出处理一件完全背包类物品的过程伪代码，以后会用到：

procedure CompletePack(c,w)
    for j=c..V
        f[j]=max{f[j],f[j-c]+w}

思想

类似01背包，只不过多一层循环，枚举第i件物品取k份(k=1,k++,j-k*w[i]>=0)

注意

观察f[i][j]中保存的信息，我们可以把k循环去掉，请思考！

例题

设有n 种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M ，今从n 种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M ，而价值的和为最大。

解决

#include <bits/stdc++.h>
using namespace std;
int m, n, w[205], c[205], f[205][205];

int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> c[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j < w[i])
                f[i][j] = f[i - 1][j];

            else if (f[i - 1][j] > f[i][j - w[i]] + c[i])
                f[i][j] = f[i - 1][j];
            else
                f[i][j] = f[i][j - w[i]] + c[i];
        }
    }

    cout << "max=" << f[n][m];
    return 0;
}

多重背包

思想

类似完全背包，只不过k循环，枚举第i件物品取k份的条件改变了

注意

观察f[i][j]中保存的信息和题目，我们不可以把k循环去掉，请思考！

例题

第一行二个数n(n≤500)，m(m≤6000)，其中n代表希望购买的奖品的种数，m表示拨款金额。

接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0件到s件均可），其中v≤100，w≤1000，s≤10。 求此次购买能获得的最大的价值（注意！不是价格）。

解决

#include <bits/stdc++.h>
using namespace std;
int m, n, w[10005], c[10005], f[10005], s[10005];

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

    cout << f[m];
    return 0;
}