#include<bits/stdc++.h> using namespace std; int a[105]; int ans[105]; int n,s,t; bool flag=false; void dfs(int depth,int x,int w){//到depth，选取了x，重量为w if(ws){ for(int i=1;i<=x;i++){ cout<<ans[i]<<" "; flag=true; } return; } else{ if(w>s||depth>n||flagtrue) return ;//剪枝 ans[x+1]=a[depth]; dfs(depth+1,x+1,w+a[depth]);//要这个物品 dfs(depth+1,x,w); } } int main(){ }

题目是错题，理论上无解，所有题解都可以被卡到 O(2n)O(2^n)O(2n). 如果没有要求必须找到第一组解，一个可行的代码如下：

#include <bits/stdc++.h> using namespace std; const int MAX_N = 105; int weights[MAX_N]; int selectedWeights[MAX_N]; int itemCount, targetWeight; bool solutionFound = false; void dfs(int depth, int selectedCount, int currentWeight) { if (currentWeight == targetWeight) { for (int i = 1; i <= selectedCount; i++) { cout << selectedWeights[i] << " "; solutionFound = true; } cout << endl; return; } else { if (currentWeight > targetWeight || depth > itemCount || solutionFound == true) return; selectedWeights[selectedCount + 1] = weights[depth]; dfs(depth + 1, selectedCount + 1, currentWeight + weights[depth]); dfs(depth + 1, selectedCount, currentWeight); } } int main() { cin >> itemCount >> targetWeight; for (int i = 1; i <= itemCount; i++) { cin >> weights[i]; } dfs(1, 0, 0); if (!solutionFound) { cout << "No Answer!" << endl; } } 链接描述