背包问题C++递归算算法？（求出所有解）

来源：百度知道 编辑：UC知道 时间：2024/05/23 20:02:46
背包问题”的基本描述是：有一个背包，能盛放的物品总重量为 S，设有 N 件物品，其重量分别为w1，w2，...，wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于 S 。
小弟用递归只能求出一组解。高手指点一下。（有其它的方法也可以）
大家搞的这么麻烦。。。哎。。。 我已经解决了。。。

#include <fstream>
#include <vector>
#include <algorithm>
#include <time>
#include <queue>
#include <string>

using namespace std;

ofstream cout("out.txt");

struct Item
{
int v, w;
int x;
Item(int val = 0, int weight = 1, int sel = 0): v(val), w(weight), x(sel) {}
};

bool operator<(const Item& a, const Item& b)
{
return double(a.v) / a.w < double(b.v) / b.w;
}

struct Node
{
unsigned level;
int val;

int B;
int cv, cw;

Node *parent, *lson, *rson;
Node(int L, int V, Node* p):
level(L), val(V), parent(p), lson(0), rson(0) {}
};

class KnapsackBase
{
protected:
vector<Item> Items;
int Cap;
int MaxV;

int cw, cv; // for later use.