/*
有N件物品，每件物品都有相应的重量，现在有一个背包，
背包只能装count公斤的物品，问背包装满count公斤，有多
少中装法？物品不得重复。
*/
#include <iostream> using namespace std;
#define N 8 //N为 多少件物品 int array[8] = {1,2,3,4,5,6,7,8}; //每个物品的重量
int count = 10; //要求装10公斤的物品
typedef struct stack { int top; int max; int * ptr; }stack;
void init(stack & mystack) { mystack.top = -1; mystack.max = 10; mystack.ptr = new int[mystack.max]; } void push(stack & mystack,int value) { if (mystack.top < mystack.max) { mystack.top++; mystack.ptr[mystack.top] = value; } }
int pop(stack & mystack) { int value = 0; if ( mystack.top == -1) return value; else { value = mystack.ptr[mystack.top]; mystack.top--; } return value; }
int isempty(stack & mystack) { if (mystack.top == -1) return -1; else return 0; }
void traver(stack & mystack) { int i = 0; while ( i<=mystack.top ) { cout<<array[mystack.ptr[i]]<<" "; i++; } cout<<endl; }
int main(int argc, char* argv[]) {
int i=0; stack mystack;
init(mystack); /*当栈非空，或者栈空，但未遍历完array时*/ while ( !isempty(mystack) || isempty(mystack)&&i<N ) { while (count > 0 && i<N) //当余下的重量还大于0时，且还未遍历完array时 { count-=array[i]; //余下的重量减去将入栈的物品重量 push(mystack,i); //入栈 i++; //array往后遍历 } if (count == 0) //如果达到要求，则输出 { traver(mystack); } i = pop(mystack); //此时必然要出栈一个 count+=array[i]; //余下的重量加出栈的物品重量 i++; //array往后遍历 }
return 0; }
