1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
#include <iostream> #include <sstream> #include <string> #include <vector> #include <stack> #include <cstdio> #define INF 100000000 using namespace std; int arr[25]; int res[25]; int SZ; vector<int> vb; bool visit[25]; int ind; int MN; void backtrack(int remaining,int index) { if(remaining<MN) { MN = remaining; SZ = vb.size(); for(int i=0;i<SZ;i++) { res[i] = vb[i]; } } for(int i=index+1;i<ind;i++) { if(visit[i]==0) { if(remaining - arr[i]<0) { continue; } vb.push_back(arr[i]); visit[i] = true; remaining = remaining - arr[i]; backtrack(remaining,i); visit[i] = false; vb.pop_back(); remaining = remaining + arr[i]; } } } int main() { int n,remaining; stringstream ss; string s; for(int i=0;i<25;i++) visit[i] = false; while(scanf("%d",&arr[0])!=EOF) { cin>>arr[1];// ind=2;// for(int i=0;i<arr[1];i++)// cin>>arr[ind++]; remaining = arr[0]; MN = INF; for(int i=2;i<ind;i++) { if(visit[i]==0) { if(remaining - arr[i]<0) { continue; } visit[i] = true; vb.push_back(arr[i]); remaining = remaining - arr[i]; backtrack(remaining,i); visit[i] = false; remaining = remaining + arr[i]; vb.pop_back(); } } for(int i=0;i<SZ;i++) cout<<res[i]<<" "; cout<<"sum:"<<arr[0] - MN<<"\n"; } return 0; } |