A136 背包问题
2025-10-02 16:19:47
发布于：浙江
15阅读
0回复
0点赞
A136 背包问题 谁能过呀
我写的不对吗？有没有人看下，一直没过
#include <iostream>
#include <vector>
using namespace std;
int n, s;
vector<int> weights;
vector<int> path;
bool found = false;
void backtrack(int index, int current_sum) {
if (found) return;
if (current_sum == s) {
for (int i = 0; i < path.size(); ++i) {
if (i > 0) cout << " ";
cout << path[i];
}
cout << endl;
found = true;
return;
}
if (current_sum > s || index == n) {
return;
}
path.push_back(weights[index]);
backtrack(index + 1, current_sum + weights[index]);
if (!found) {
path.pop_back();
backtrack(index + 1, current_sum);
}
}
int main() {
cin >> n >> s;
weights.resize(n);
for (int i = 0; i < n; ++i) {
cin >> weights[i];
}
backtrack(0, 0);
if (!found) {
cout << "NoAnswer!" << endl;
}
return 0;
}
有帮助，赞一个