本篇博客简述背包问题的部分内容，详情请参考崔添翼老师的背包问题九讲教材，借助 Acwing 上的题总结一下模板

01背包问题

题目

基本思路

最基本的背包问题，特点是：每种物品仅有一件，可以选择放或者不放

定义子问题状态为 dp[i][j] 表示前 i 件物品放入一个容量为 j 的背包可以获得的最大价值。则其状态转移方程便是：dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])

这个方程最为重要，它的思想贯穿整个背包问题，基本上所有跟背包相关的问题都由这个方程衍生出来。若只考虑第 i 件物品的策略（放与不放）那么可以转化为一个只和前 i-1 物品相关的问题。如果不放第 i 件物品那么问题转化为前 i-1 件物品放入容量为 j 的背包中，价值也就是 dp[i-1,j]；如果放第 i 件物品那么问题就转化为前 i-1 件物品放入剩余容量为 j-v[i] 的背包中，此时能获得的最大价值就是 dp[i-1][j-v[i]] 再加上放入当前第 i 件物品获得的价值 w[i]

时间复杂度与空间复杂度均为 O(VN)

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define debug(x) cout << "debug: " << x << endl;
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 5;

int v[maxn], w[maxn], dp[maxn][maxn];	//第一维物品第二位容量

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; ++i) {      //第i轮装入第i个物品
        for (int j = 0; j <= V; ++j) {  //枚举可能背包的容量
            if (j < v[i])               //当前物品装不下
                dp[i][j] = dp[i - 1][j];
            else  //装的下该物品有两种策略
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << dp[n][V] << endl;
    return 0;
}

优化空间复杂度

上述思想时间复杂度无法优化，但是空间复杂度可以进一步优化到 O(V)。对于 dp[i][j] 这个状态来说其实就是从上一次循环（也就是求解出来的放入 i-1 物品是的不同容量状态）的两个子问题 dp[i-1][j] 和 dp[i-1][j-v[i]] 递推出来。实际上为什么上述代码需要开两维就是在求解当前第 i 个物品在不同容量下的问题时需要用到上一轮已经求出来的第 i-1 个物品在不同容量下的问题，如果我们将第二维由大到小逆向循环则可以实现降调第一维的同时仍然保证遵从上述思想的递推，相当于求解每轮第 i 个物品在容量 j 的问题后直接覆盖掉之前存储的第 i-1 物品并保证以后再也不需要用到第 i-1 物品在容量 j 的子问题了。

正向与逆向循环是滚动数组降维的关键问题，这里博主已经理解透彻固不详细展开讲解，不明白的话一定要查找相关博客完全理解，后面的背包问题基本都采用了该思想优化空间

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define debug(x) cout << "debug: " << x << endl;
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 5;

int v[maxn], w[maxn], dp[maxn];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[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]);
    }
    cout << dp[V] << endl;
    // system("pause");
    return 0;
}

同时由于是覆盖问题，当前容量不能放下该物品的时候就仍然与上一轮物品在当前容量的结果一样，所有不需要覆盖，因此第二维循环的时候覆盖更新到 v[i] 即可。

初始化细节问题

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

如果是第一种问法要求恰好装满背包，那么初始化的时候除了 dp[0] 为 0，其他的位置应该设为 -inf，这样就可以保证最终得到的 dp[V] 是一种恰好装满背包的最优解，因为只有从 dp[0] 转移过来的状态才是符合题意的状态，从其他初始位置转移过来说明背包没有被装满，也就不符合题意直接设为负无穷保证计算的答案不影响最终结果。

如果是第二种问法那么背包并非必须被装满，那么任何容量的初始背包位置都是合法的（因为可以什么都不装），进而从任何位置计算出来的结果都可以作为答案，所以初始状态也就全部为 0。

这个技巧完全可以推广到其他类型的背包问题作为一个变式，后面不再对状态转移的初始化问题进行讲解

一个常数优化

上述第二重循环的下限仍然可以被优化：for(int j=V;j>=max(V-sum(v[i+1...n]),v[i]);--j)。只需要知道最后第 n 件物品不同容量下 dp[j] 的值，倒推前一个物品其实只要知道 dp[j-v[n]] 即可，依此类推对于第 i 个物品我们只要知道 dp[j-sum[v[i+1...n]]] 即可，当然了这个容量如果小于 v[i] 了那么可以提前终止。对于这种多次需要区间的求和，我们可以用一个前缀和预处理解决。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define debug(x) cout << "debug: " << x << endl;
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 5;

int v[maxn], w[maxn], dp[maxn], sum[maxn];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i], sum[i] = sum[i - 1] + v[i];
    for (int i = 1; i <= n; ++i) {
        int bound = max(v[i], V - (sum[n] - sum[i]));   //前缀和处理
        for (int j = V; j >= bound; --j)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
    cout << dp[V] << endl;
    return 0;
}

完全背包问题

题目

完全背包模板题

基本思路

和 01背包问题的区别就是每种不同的有无限件了，也就是从每种物品的角度考虑与它相关的策略已并非取或者不取两种，而是有取 0 件、1 件、2 件……直至取 [V/v[i]] 件等多种选法。如果仍然按照 01背包时的思路另 dp[i][j] 表示前 i 种物品放入一个容量为 v 的背包的最大权值。仍然可以按照每种物品的不同策略写出状态转移方程：dp[i][j]=max(dp[i-1][j-k*v[i]]+k*w[i]) 0<=k*v[i]<=j

这与 01背包问题一样有 O(VN) 个状态需要求解，但求解每个状态的时间已经不再是尝试了，求解状态的 dp[i][j] 时间是 O(j/v[i])，总的时间复杂度可以认为是 $O(NV\sum \frac{V}{v[i]} )$ ，可以说非常的大。将 01背包的基本思路改进得到这个清晰的方法说明 01背包问题的方程的确是很重要的，可以推及其他类型的背包问题但是我们还是要改进这个复杂度。

一个简单有效的优化

无疑对于这种情况：若两件物品 i、j 满足 v[i]<=v[j] 且 w[i]>=w[j] 则可以直接将 j 物品扔掉不去考虑。对于随机生成的数据这种方法往往能大大减少物品的件数从而加快速度。然而并不能改善最坏情况的复杂度因为有可能出题人特别设计数据保证一件物品也扔不掉。

这个优化可以简单的 O(N²) 的实现，一般题目的时间范围都是可以承受的。另外针对背包问题还有一个比较不错的方法是：将费用本身就大于 V 的物品直接扔掉，然后用类似计数排序的做法计算出对于费用相同的物品中价值最高的是哪个，可以 O(V+N) 的完成这个优化。

转化 01背包问题求解

直接将完全背包问题考虑转化为 01背包问题求解。

最简单的想法是考虑到第 i 种物品最多选择 [V/v[i]] 件于是可以把第 i 种物品转化为 [V/v[i]] 件费用及价值均相同的物品，然后套用 01背包问题求解。这样的做法完全没有改进时间复杂度，但是这种做法也说明了完全背包问题确实可以转化为 01背包问题思路：
另一种更高效的方法是把第 i 中物品拆解成费用为 v[i]*2^k 与价值为 w[i]*2^k 的若干件物品，其中 k 取遍满足 v[i]*2^k<=V 的非负整数。这其实二进制的思想，因为不管最优策略选择几件第 i 种物品，其件数都可以表示为二进制，也就是若干个 2^k 件物品的和。这样一来就把每种物品拆解成 O(log[V/v[i]]) 件物品，复杂度改进非常有效

O(VN)算法

将优化空间复杂度后的 01背包代码循环正向即可求解出完全背包问题。简单讲一下为什么成立？实际上就是正向与逆向循环覆盖问题的区别，01 背包问题因为每件物品只能用 1 次所以循环覆盖必须保证求解当前容量为 j 第 i 件物品的时候从上次循环的容量转移为没有用第 i 件物品，所以逆序的话保证了覆盖叠加是由上一轮没有放过第 i 件物品的两个体积转移过来。现在正向过来覆盖叠加正好是可以从上一轮可以放过第 i 件物品的两个体积转移过来，那么无数次也就是每次循环都正向即保证了可能用很多次，恰好符合我们完全背包的题目。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define debug(x) cout << "debug: " << x << endl;
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 5;

int v[maxn], w[maxn], dp[maxn];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; ++i) {
        for (int j = v[i]; j <= V; ++j)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
    cout << dp[V] << endl;
    // system("pause");
    return 0;
}

多重背包问题

题目

多重背包模板题

基本思路

仍然利用完全背包问题的基本思想，将方程的系数调整一下：dp[i][j]=max(dp[i-1][v-k*v[i]])+k*w[i]) 0<=k<=s[i]，因为对于第 i 个物品有 m[i]+1 中策略。所以复杂度为 $O(V\sum M_{i} )$

转化为 01背包问题

一种好想好写的基本方法就是转化为 01背包问题求解：把第 i 种物品转换成 m[i] 件 01背包中的物品，但是这样直接求解复杂度依旧不变
考虑采用二进制拆分的策略。把第 i 种物品换成若干件物品，使得原问题中第 i 种物品可取的每种策略——取 [0…m[i]] 件——均能等价于取若干件代换以后的物品，同时取超过 m[i] 件的策略必不能出现。方法是：将第 i 种物品分成若干件 01背包中的物品，其中每种物品有一个系数。这件物品的费用和价值均是原来的费用和价值乘以这个系数。另这些系数分别为 1,2,2²,…,2^k-1,m[i]-2^k+1，且k是满足 m[i]-2^k+1 的最大整数。因为是二进制的拆解所以物品也就分成了 O(logm[i])种物品，将原问题转换为了复杂度为 $O(V \sum logm[i])$ 的 01背包问题。

其实就是从最小的二进制一直拆解直至最后剩余的数不能再往后拆解，这些数组成的系数就可以实现几个组合表示一个小于 m[i] 的数，也就达到了物品被拆解为几个物品目的

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define debug(x) cout << "debug: " << x << endl;
using namespace std;
typedef long long ll;
const int maxn = 1005;

int v[maxn], w[maxn], s[maxn], dp[2005];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= n; ++i) {
        int num = min(s[i], V / v[i]);
        for (int k = 1; num > 0; k <<= 1) {
            if (k > num) k = num;
            num -= k;
            for (int j = V; j >= v[i] * k; --j)
                dp[j] = max(dp[j], dp[j - v[i] * k] + k * w[i]);
        }
    }
    cout << dp[V] << endl;
    return 0;
}

O(VN)算法

一般情况下上述的算法已经可以满足大部分问题

通过使用单调队列的数据结构我们可以将每个状态的值均摊为 O(1) 的时间求解。博主能力欠佳还不是很好的理解该算法的思想，这里给出一个学习时自认为讲的非常清楚的视频👇

多重背包单调队列优化

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define debug(x) cout << "debug: " << x << endl;
using namespace std;
typedef long long ll;
const int maxn = 1005;

int v[maxn], w[maxn], s[maxn], q[20005], f[20005], g[20005];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; ++i)
        cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= n; ++i) {  //n个物品
        memcpy(g, f, sizeof f); //拷贝旧的f
        for (int j = 0; j < v[i]; ++j) {  //最多有v个分组
            int head = 0, tail = -1;
            for (int k = j; k <= V; k += v[i]) {//正序实现多重背包
                if (head <= tail && q[head] < k - s[i] * v[i]) ++head;  //看看是否用来更新f的旧得g的最大在窗口中
                if (head <= tail) f[k] = max(g[k], g[q[head]] + (k - q[head]) / v[i] * w[i]);   //取出窗口中最大的g更新f
                while (head <= tail && g[k] >= g[q[tail]] + (k - q[tail]) / v[i] * w[i]) --tail;    //维护g窗口的最大值
                q[++tail] = k;  //当前g元素入队
            }
        }
    }
    cout << f[V] << endl;
    // system("pause");
    return 0;
}

混合背包问题

题目

混合背包模板题

01背包与完全背包混合

两者的代码只有第二重循环的方向不同，一类物品只能取一次，另一类物品可以取无限次，只需要对每个物品应用各自的转移方程即可。

再加上多重背包

在代码中再加上多重背包的单调队列算法即可实现混合背包的整体 O(VN) 复杂度。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define debug(x) cout << "debug: " << x << endl;
using namespace std;
typedef long long ll;
const int maxn = 1005;

int v[maxn], w[maxn], s[maxn], dp[maxn];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; ++i)
        cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= n; ++i) {
        if (s[i] == 0)
            for (int j = v[i]; j <= V; ++j)
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        else if (s[i] != -1) {
            int num = min(s[i], V / v[i]);
            for (int k = 1; num > 0; k <<= 1) {
                if (k > num) k = num;
                num -= k;
                for (int c = V; c >= v[i] * k; --c)
                    dp[c] = max(dp[c], dp[c - v[i] * k] + w[i] * k);
            }
        } else
            for (int j = V; j >= v[i]; --j)
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
    cout << dp[V] << endl;
    // system("pause");
    return 0;
}

二维费用背包

题目

二维费用背包模板题

基本思路

费用加了一维，只需要状态也加上一维即可。利用上述降维的思想可以开二维数组分别记录两个费用状态即可，如果费用是01背包形式则逆向循环，如果是完全背包形式则正向循环，如果是多重背包形式就二进制拆分。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define debug(x) cout << "debug: " << x << endl;
using namespace std;
typedef long long ll;
const int maxn = 1005;

int v[maxn], m[maxn], w[maxn], dp[maxn][maxn];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, V, M;
    cin >> n >> V >> M;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> m[i] >> w[i];
    for (int i = 1; i <= n; ++i)
        for (int j = V; j >= v[i]; --j)
            for (int k = M; k >= m[i]; --k)
                dp[j][k] = max(dp[j][k], dp[j - v[i]][k - m[i]] + w[i]);
    cout << dp[V][M] << endl;
    // system("pause");
    return 0;
}

分组背包问题

题目

分组背包模板题

基本思路

这个问题变成了每组物品有若干种策略：是选择本组的某一件还是一件不选。用 dp[i][j] 表示前 i 组物品花费费用 j 的最大权值，那么就有如下代码（采用降维将外层状态消去）

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define debug(x) cout << "debug: " << x << endl;
using namespace std;
typedef long long ll;
const int maxn = 105;

struct node {
    int v, w;
    node(int v, int w) : v(v), w(w) {}
};

int dp[maxn];
vector<node> beg[maxn];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) {
        int s;
        cin >> s;
        for (int j = 1; j <= s; ++j) {
            int x, y;
            cin >> x >> y;
            beg[i].push_back(node(x, y));
        }
    }
    for (int i = 1; i <= n; ++i)
        for (int j = V; j >= 0; --j)
            for (auto e : beg[i]) {
                if (e.v > j) continue;
                dp[j] = max(dp[j], dp[j - e.v] + e.w);
            }
    cout << dp[V] << endl;
    // system("pause");
    return 0;
}

实际上就是对于每组物品尝试拿改组内的某一个物品来更新权值

有依赖的背包问题

题目

有依赖的背包模板题

基本思路

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define debug(x) cout << "debug: " << x << endl;
using namespace std;
typedef long long ll;
const int maxn = 115;

int n, V;
int v[maxn], w[maxn], dp[maxn][maxn];
struct edge {
    int to, nex;
} E[maxn];
int head[maxn], tot;

inline void init() {
    tot = 0;
    memset(head, -1, sizeof head);
}

inline void add(int x, int y) {
    ++tot;
    E[tot].nex = head[x];
    head[x] = tot;
    E[tot].to = y;
}

void dfs(int rt) {  //选当前节点的最大值价值
    for (int i = head[rt]; ~i; i = E[i].nex) {
        int e = E[i].to;                     //当前节点的子节点
        dfs(e);                              //先搜索出子节点的最大价值
        for (int j = V - v[rt]; j >= 0; --j)  //01枚举当前不同剩余体积
            for (int k = 0; k <= j; ++k)     //枚举处理出来的子节点的分组,不同体积对应不同的子节点分组情况
                dp[rt][j] = max(dp[rt][j], dp[rt][j - k] + dp[e][k]);
    }
    for (int i = V; i >= v[rt]; --i) dp[rt][i] = dp[rt][i - v[rt]] + w[rt];  //因为是默认选择当前节点了所以要加上当前节点的价值
    for (int i = 0; i < v[rt]; ++i) dp[rt][i] = 0;                           //不能加上当前节点的体积价值就是0
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> V;
    init();
    int p, root;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i] >> w[i] >> p;
        if (p == -1)
            root = i;
        else
            add(p, i);
    }
    dfs(root);
    cout << dp[root][V] << endl;
    // system("pause");
    return 0;
}

以上涉及的各种背包问题都是要求在背包容量（费用）的限制下可以取到的最大价值但是背包问题还有很多种灵活的问法，在这里简单的提一下常用的几个问题，其实只要理解了求背包问题最大价值的方法，即使问法变化了也是不难想出算法的。

背包问题求方案数

题目

背包问题求方案数模板题

基本思路

对于一个给定了背包容量、物品费用、物品间相互关系（分组、依赖等）的背包问题，除了再给定某个物品的价值后求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。对于这类改变问法的问题，一般只需将状态转移方程中的 max 改成 sum 即可。

例如上述的题可以再开一个 cnt 数组再每次求不同状态的背包权值同时求出方案数的变化，同样采用降维。初始化的状态应该是第 0 个物品在容量为 0 的情况下只有唯一的选法。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define debug(x) cout << "debug: " << x << endl;
using namespace std;
typedef long long ll;
const int maxn = 1005;
const int mod = 1e9 + 7;

int v[maxn], w[maxn];
int dp[maxn], cnt[maxn];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, V;
    cin >> n >> V;
    for (int i = 0; i <= V; ++i) cnt[i] = 1;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; ++i) {
        for (int j = V; j >= v[i]; --j) {
            if (dp[j - v[i]] + w[i] > dp[j])
                dp[j] = dp[j - v[i]] + w[i], cnt[j] = cnt[j - v[i]];
            else if (dp[j - v[i]] + w[i] == dp[j])
                cnt[j] = (cnt[j] + cnt[j - v[i]]) % mod;
        }
    }
    cout << cnt[V] << endl;
    // system("pause");
    return 0;
}

背包问题求具体方案

题目

背包问题求具体方案模板题

基本思路

字典序最小的最优方案也就是选择的方案获得权值最大的同时路径的排列字典序最小

一种方法是开一个数组记录不同状态是由之前哪个状态转移过来的，那么寻找方案数的时候根据这个数组进行路径的打印即可
另一种方法：计算完各个状态后可以肯定 dp[1][V] 是最大价值，那么我们便开始考虑能够选取第一个物品。如果 dp[1][V]==dp[2][V-v[1]]+w[i]，也就是说选取了第一个物品可以转移到第二个物品的最优解，又因为需简要满足字典序最小所以当前肯定是满足得到权值最优解而且字典序最小的选法所以一定选择此物品。如果 dp[1][V]==dp[2][V]，也就是说当前物品不选择是转移到第二个物品的最优解，所以跳过此物品。如此从第一个物品的 V 状态向后转移最终打印出来的就是字典序最小的最优方案。中间可以进行一些优化：当背包已经满了说明后面的物品肯定都不选了所以提前结束打印。另外需要注意最后一个物品，如果前一个物品最优解状态剩余容量放得下最后一个物品那肯定拿

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define debug(x) cout << "debug: " << x << endl;
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 5;

int v[maxn], w[maxn], dp[maxn][maxn];   //维护的是从第i个物品到第n个物品在剩余容量为j的情况下能得到的最大价值

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
    for (int i = n; i >= 1; --i)
        for (int j = 0; j <= V; ++j) {
            dp[i][j] = dp[i + 1][j];
            if (j >= v[i])
                dp[i][j] = max(dp[i][j], dp[i + 1][j - v[i]] + w[i]);
        }
    int p = V;
    for (int i = 1; i <= n; ++i) {
        if (p == 0) //背包满了直接退出
            break;  
        else if (i == n && p >= v[i]) { //特判最后一个物品需不需要装进背包
            cout << i << ' ';
            break;
        } else if (p >= v[i] && dp[i][p] == dp[i + 1][p - v[i]] + w[i]) {   //说明可以装下这个物品且装下后满足最优
            cout << i << ' ';
            p -= v[i];
        }
    }
    cout << endl;
    // system("pause");
    return 0;
}

背包问题求第K优解

题目

背包问题求第K优解模板题

基本思路

相应的最优问题能够写出状态方程用动态规划方法解决，那么求第K优解问题比最优解的复杂度多一个系数K。基本思想是，将每个状态都表示成有序队列，将状态方程中的 max/min 转化成一个有序队列合并。以 01背包举例，求最优解的状态方程是 dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])，相当于是那和不拿的两种情况（也就是长度为1的序列）的最优解中取最优作为当前状态的最优解。那么同理如果要求第K优解状态时应该从两种策略的前K优解序列中取第K优解，所以在状态再开一维记录前K优解，然后我们需要做的就是在两个序列合并中取前K优解作为当前状态的前K优解。合并的方法就是用两个遍历指针分别从两个序列一端开始比较选择出前K大/前K小的解，最终的答案就是 dp[n][V][K]，总的时间复杂度为 O(NVK)。

为什么这个方法正确呢？实际上，一个正确的状态转移方程的求解过程遍历了所有可用的策略，也就覆盖了问题的所有方案。只不过由于是求最优解，所以其他在任何一个策略上达不到最优的方案都被忽略了，如果把每个状态表示成一个大小为K的数组，并在这个数组中有序的保存该状态可取的前K个最优解，那么对任两个状态的 max/min 运算等价于两个由大到小的有序队列的合并。

另外还需要注意的是题目对于第K优解定义，将策略不同但权值相同的两个方案是看做同一个解还是不同的，如果是前者还需要在求解当前状态的有序队列时保证没有重复的数。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define endl "\n"
#define online_judge
#define debug(x) cout << "debug: " << x << endl;
using namespace std;
typedef long long ll;
const int maxn = 35;
int v[105], w[105];
ll a[maxn], b[maxn], dp[1005][maxn];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
#ifndef online_judge
    freopen("IO\\in.txt", "r", stdin);
    freopen("IO\\out.txt", "w", stdout);
#endif
    int t;
    cin >> t;
    while (t--) {
        int n, V, K;
        cin >> n >> V >> K;
        for (int i = 1; i <= n; ++i) cin >> w[i];
        for (int i = 1; i <= n; ++i) cin >> v[i];
        memset(dp, 0, sizeof dp);  //题目说如果方法不足k个就是输出0所以这里初始化为0,否则一般初始化为负无穷代表不存在
        for (int i = 1; i <= n; ++i)
            for (int j = V; j >= v[i]; --j) {
                for (int k = 1; k <= K; ++k) {
                    a[k] = dp[j - v[i]][k] + w[i];  //统计出选择当前物品后的前k个解
                    b[k] = dp[j][k];                //统计出不选择当前物品后的前k个解
                }
                a[K + 1] = b[K + 1] = -1;  //限制双指针的边界
                int x, y, o;
                x = y = o = 1;  //两个遍历序列的指针以及需要求解的第o解
                while (o <= K && (a[x] != -1 || b[y] != -1)) {
                    if (a[x] > b[y])  //双指针法从两个序列中求出前k个解
                        dp[j][o] = a[x], ++x;
                    else
                        dp[j][o] = b[y], ++y;
                    if (dp[j][o] != dp[j][o - 1]) ++o;  //只有值不同才能代表找到一个解
                }
            }
        cout << dp[V][K] << endl;
    }
    return 0;
}