12. 背包问题求具体方案
思路
背包问题求具体方案类似于求最短路径问题
对于求具体方案来说，可以由最后的最大价值逆推
原因是：01背包问题的集合划分就是依靠第i个物品选不选
若选择当前物品，那么当前价值一定是由上一级的f[i - 1][j],或者f[i - 1][j - v[i]] + w[i]转化而来的
若是f[i][j] == f[i - 1][j],那么一定不选第i件物品
否则一定要选第i件物品
当然还有f[i - 1][j] == f[i - 1][j - v[i]] + w[i]的情况，
此时若没有字典序的要求，则都需要去判断，或者这两条路都可以满足题意
本题要求最小字典序，则第i个物品若能选则一定要选！
这样字典序一定最小
本题思路即将最大价值反过来存，然后从1开始往回推，这样就是正向的字典序
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N], w[N];
int n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
for (int i = n; i >= 1; i --) {
for (int j = 1; j <= m; j ++) {
f[i][j] = f[i + 1][j];
if (j >= v[i]) {
f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
}
}
}
//此时f[i][m]为最大值
int j = m;
for (int i = 1; i <= n; i ++) {
if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) {
cout << i << ' ';
j -= v[i];
}
}
return 0;
}
1013. 机器分配
思路
分组背包 + 背包问题求具体方案
分组背包和多重背包类似，都需要循环每组（种）物品个数，然后确定最大价值。
但实际代码上与01背包类似
求具体方案数：
可以是先逆序存储最大价值，然后正序由最大价值推出具体方案
也可以不改变顺序，直接推出最大价值，然后用数组存储由最大价值推出的具体方案
#include <iostream>
using namespace std;
const int N = 11, M = 16;
int f[N][M];
int w[N][M];
int n, m;
int way[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
cin >> w[i][j];
for (int i = 1; i <= n; i ++)
{
for (int j = 0; j <= m; j ++) {
f[i][j] = f[i - 1][j];
for (int k = 0; k <= m; k ++) {
if (j >= k) f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
}
}
}
cout << f[n][m] << endl;
int j = m;
for (int i = n; i >= 1; i --) {
for (int k = 0; k <= m; k ++) { //k==0表示不取当前分组的物品
if (f[i][j] == f[i - 1][j - k] + w[i][k]) {
way[i] = k;
j -= k;
break;
}
}
}
for (int i = 1; i <= n; i ++) cout << i << ' ' << way[i] << endl;
return 0;
}
426. 开心的金明
思路
金明的预算方案简化版，其实就是01背包问题
#include <iostream>
using namespace std;
const int N = 30, M = 30010;
int f[M];
int main() {
int m, n;
cin >> m >> n;
for (int i = 1; i <= n; i ++) {
int v, w;
cin >> v >> w;
w = v * w;
for (int j = m; j >= v; j --) {
f[j] = max(f[j], f[j - v] + w);
}
}
cout << f[m] << endl;
return 0;
}
487. 金明的预算方案
思路
本题是典型分组背包问题，不过枚举每组的物品方法使用的是二进制枚举法
#include <iostream>
#include <algorithm>
#include <vector>
#define v first
#define w second
using namespace std;
typedef pair<int, int> PII;
const int N = 32010, M = 65;
int f[N];
vector<PII> informal[M]; //附件
PII formal[M]; //主件
int n, m;
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i ++) {
int v, w, q;
cin >> v >> w >> q;
if (!q) formal[i] = {v, v * w};
else informal[q].push_back({v, v * w});
}
for (int i = 1; i <= n; i ++) {
if (formal[i].v) { //若该主件存在
for (int j = m; j >= 0; j --) {
//使用二进制枚举法枚举可能有的状态
for (int k = 0; k < 1 << informal[i].size(); k ++) {
int x = formal[i].v, y = formal[i].w;
//这是一组中选择某（几）件物品后，得到的体积和价值
for (int h = 0; h < informal[i].size(); h ++) {
if (k >> h & 1) {
x += informal[i][h].v;
y += informal[i][h].w;
}
}
if (j >= x) f[j] = max(f[j], f[j - x] + y);
}
}
}
}
cout << f[m] << endl;
return 0;
}