这是我学习数据结构时的一道上机作业，那时还没养成写注释的习惯，所以各位得受点苦了。
只是简易背包问题。
代码：
展开 1 // 背包问题所有解 2 // 作者:王锦 3 // 邮箱:jinksw@vip.qq.com 4 5 #include "stdafx.h" 6 #include7 #include 8 #include 9 using namespace std; 10 11 class BagProblemSolver 12 { 13 private: 14 int *stuffWeight; 15 int s; 16 int n; 17 list
*> allResultHolder;//存放所有解 18 void insertResultToList(stack bagStack); 19 public: 20 BagProblemSolver(int s,int n,int *stuffWeight) 21 { 22 this->s = s; 23 this->n = n; 24 this->stuffWeight = new int[n]; 25 for(int i = 0;i < n;++i) 26 this->stuffWeight[i] = stuffWeight[i]; 27 } 28 ~BagProblemSolver() 29 { 30 delete[] stuffWeight; 31 } 32 list
*> getAllResult(); 33 }; 34 35 list
*> BagProblemSolver::getAllResult() 36 { 37 if(s <= 0) 38 return allResultHolder; 39 int currentWeight = 0; 40 stack indexStack; 41 int i = 0; 42 do 43 { 44 while(currentWeight < s && i < n) 45 { 46 if(currentWeight + stuffWeight[i] <= s) 47 { 48 indexStack.push(i); 49 currentWeight += stuffWeight[i]; 50 } 51 i++; 52 } 53 if(currentWeight == s) 54 { 55 insertResultToList(indexStack); 56 i = indexStack.top(); 57 indexStack.pop(); 58 currentWeight -= stuffWeight[i]; 59 i++; 60 } 61 else if(!indexStack.empty()) 62 { 63 i = indexStack.top(); 64 indexStack.pop(); 65 currentWeight -= stuffWeight[i]; 66 i++; 67 } 68 }while(!indexStack.empty() || i < n); 69 return allResultHolder; 70 } 71 72 73 74 void BagProblemSolver::insertResultToList(stack bagStack) 75 { 76 stack tempStack;//用于将解以正序存入list 77 while(!bagStack.empty()) 78 { 79 tempStack.push(bagStack.top()); 80 bagStack.pop(); 81 } 82 list * resultList = new list (); 83 while(!tempStack.empty()) 84 { 85 resultList->push_back(stuffWeight[tempStack.top()]); 86 tempStack.pop(); 87 } 88 allResultHolder.push_back(resultList); 89 } 90 91 int _tmain(int argc, _TCHAR* argv[]) 92 { 93 cout << "请输入背包可以放入的物品重量.(输入q退出)" << endl; 94 char c; 95 cin >> c; 96 while(c != 'q') 97 { 98 cin.putback(c); 99 int s = 0;100 cin >> s;//背包可以放入的物品重量101 cout << "请输入物品数量." << endl;102 int n = 0;//物品数量103 cin >> n;104 int *stuffWeight= new int[n];105 cout << "请分别输入" << n << "个物品重量." << endl;106 for(int i = 0;i < n;++i)107 cin >> stuffWeight[i];108 BagProblemSolver test(s,n,stuffWeight);109 list
*> ls = test.getAllResult();110 cout << "背包容量(" << s << "),有(" << n << ")个物品,";111 cout << "质量分别为(";112 for(int i = 0; i < n;++i)113 {114 cout << stuffWeight[i];115 if(i != n - 1)116 cout << ",";117 } 118 cout << ")" << endl;119 if(ls.empty())120 {121 cout << "此问题无解!" << endl;122 }123 else124 {125 cout << "所有解为:" << endl;126 while(!ls.empty())127 {128 list *temp = ls.front();129 ls.pop_front();130 while(!temp->empty())131 {132 cout << temp->front() << " ";133 temp->pop_front();134 }135 cout << endl;136 delete temp;137 }138 }139 cout << "请输入背包可以放入的物品重量.(输入q退出)" << endl;140 cin >> c;141 }142 }