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;
}