PTA 7-2 0/1背包问题(回溯法) 作者 王东 单位 贵州师范学院
0/1背包问题。给定一载重量为W的背包及n个重量为wi、价值为vi的物体，1≤i≤n,要求重量和恰好为W具有最大的价值。
输入格式:
第一行输入背包载重量W及背包个数n，再依次输入n行，每行为背包重量wi和价值vi。
输出格式:
第一行输出装入背包内的物体编号(末尾有空格),若没有任何物品能装入，输出: No，第二行输出背包内的物体总价值。
输入样例1:
5 10
2 6
2 3
6 5
5 4
4 6
输出样例1:
1 2 3
14
输入样例2:
2 10
11 2
13 100
输出样例2:
No
0 学校老师给的题目与网上有一点偏差，但区别不大。
本题思路参考自这篇文章：7-12 0/1背包问题 (30 分)_给定一载重量为w的背包及n个重量为wi、价值为vi的物体,1≤i≤n,要求而且重量和恰-CSDN博客
修改后符合本题的代码如下：
#include <bits/stdc++.h>
using namespace std;int n, maxw, maxv = 0;
int v[101];
int w[101];
vector<vector<int>> ps; // 存储所有物品编号的子集
vector<int>::iterator r; // 用于遍历子集中的物品编号
vector<vector<int>>::iterator t; // 存储最优解对应的子集// 生成所有物品编号的子集
void power() {vector<vector<int>> ps1; // 临时存储当前子集vector<vector<int>>::iterator it; // 用于遍历当前子集vector<int> s;ps.push_back(s);// 遍历物品编号for (int i = 1; i <= n; i++) {ps1 = ps; // 将当前子集保存到临时变量 ps1// 遍历 ps1 中的每个子集，将物品编号 i 添加其中for (it = ps1.begin(); it != ps1.end(); it++) {(*it).push_back(i); // 向子集中添加物品编号i}// 将扩展后的子集加入psfor (it = ps1.begin(); it != ps1.end(); it++) {ps.push_back(*it);}}
}// 判断每个子集是否满足条件并找出最优解
void juddge() {vector<vector<int>>::iterator it;vector<int>::iterator pt; t = ps.end(); // 遍历所有子集for (it = ps.begin(); it != ps.end(); it++) {int sumv = 0; // 当前子集的总价值int sumw = 0; // 当前子集的总重量// 遍历当前子集中的物品编号for (pt = (*it).begin(); pt != (*it).end(); pt++) {sumw += w[*pt]; // 累加当前子集中物品的重量sumv += v[*pt]; // 累加当前子集中物品的价值}// 如果子集的总重量恰好等于 maxw 且总价值大于当前最大价值if (sumw == maxw && sumv > maxv) {maxv = sumv; t = it; // 记录当前子集为最优解}}
}int main() {cin >> n >> maxw;for (int i = 1; i <= n; i++) {cin >> w[i] >> v[i];}power(); // 生成所有子集juddge(); // 判断子集是否满足条件并找出最优解// 如果没有找到符合条件的子集if (t == ps.end()) {cout << "No" << endl; // 输出 Nocout << "0"; // 输出总价值为0}else {// 输出最优解中的物品编号for (r = (*t).begin(); r != (*t).end(); r++) {cout << *r << " ";}cout << endl;cout << maxv;}return 0;
}