不考虑价值背包问题

@最简单不考虑价值背包问题

原题目为

假设有一个能装入总体积为T的背包和N件体积分别任w1、w2、w3、……wn的物品，能否从n件物品中挑选若干件恰好装满背包，即w1+w2+……Wn = T，要求满足上述条件的解。

例如，当T = 10，各件物品的体积为{1、8、4、3、5、2}时，可以 找到下列4组解： (1,4,3,2)、(1，4，5)、(8，2)、(3，5，2)

代码如下

#include<iostream> #include <stdlib.h> using namespace std; class Stack { private: int vleft; //剩余空间 int vmax; //总空间 int maxsize; //栈的最大空间 int *base; //栈底指针 int top; //栈顶指针 public: Stack(int size,int t) //栈的定义 { vmax = t; vleft = t; maxsize = size; base = new int[maxsize]; if(base==NULL) { cout << "分配内存失败"; exit(0); } top = 0; } void Push(int &e) //将元素e入栈 { base[top++] = e; vleft -= e; } void Pop() //出栈 { vleft += base[--top]; } void output() { for (int j = 0; j < top; j++) { cout << base[j] << " "; if (j == top - 1) cout << endl; } } int judge() { if (vleft > 0) return 1; if (vleft == 0) return 2; if (vleft < 0) return 3; } bool judge1(int q) { if (vleft >= q) { return true; } else { return false; } // 或者直接 return vleft>=q; } }; int main() { int n; cout << "请输入物品个数" << endl; cin >> n; int t; cout << "请输入背包体积" << endl; cin >> t; Stack Bag(n,t); //定义栈的背包对象 int *p; p = new int[n]; int *pp; pp = new int[n]; for (int j = 0; j < n; j++) { pp[j] = 0; } for (int j = 0; j < n; j++) { cout << "请输入物品大小" << endl; cin >> p[j]; } int i = 0; int l = 0; for (i = 0; i < n; i++) { if (Bag.judge1(p[i])) { Bag.Push(p[i]); pp[l] = i; l++; i++; break; } } int j; while (l>=0) { j = pp[l] + 1; while(Bag.judge()<3 && j<n) { Bag.Push(p[j]); pp[l] = j; l++; if (Bag.judge() == 2) { Bag.output(); /*system("pause");*/ Bag.Pop(); j++; l--; } else if (Bag.judge() < 3) j++; else { Bag.Pop(); l--; j++; } } Bag.Pop(); l--; } getchar(); return 0; }