0-1背包问题（回溯法）

#if 1
#include
#include
using namespace std;
template
class Knap {
friend Typep Knapsack(Typep*, Typew*, Typep, int);
private:
Typep Bound(int i);
void Backtrack(int i);
Typew c;//背包容量
int n;//物品数
Typew* w;//物品重量数组
Typep* p;//物品价值数组
Typew cw;//当前重量
Typep cp;//当前价值
Typep bestp;//当前最优价值
};
template
void Knap::Backtrack(int i) {
if (i > n) {
bestp = cp;
return;
}
if (cw + w[i] <= c) {//进入左子树
cw += w[i];
cp += p[i];
Backtrack(i + 1);
cw -= w[i];
cp -= p[i];
}
if (Bound(i + 1) > bestp)//进入左子树
Backtrack(i + 1);
}
template
Typep Knap::Bound(int i) {
//计算上届
Typew cleft = c - cw;//剩余容量
Typep b = cp;
//一物品单位重量价值递减序装入物品
while (i <= n && w[i] <= cleft) {
cleft -= w[i];
b += p[i];
i++;
}
//背包装满
if (i <= n)
b += p[i] * cleft / w[i];
return b;
}
template
class Object {
friend Typep Knapsack(Typep*, Typew*, Typep, int);
public:
int operator<=(Object a)const {
return(d >= a.d);
}
private:
int ID;
float d;
};
template
Typep Knapsack(Typep* p, Typew* w, Typew c, int n) {
Typew W = 0;
Typep P = 0;
Object* Q = new Object[n];
for (auto i = 1; i <= n; i++) {
Q[i - 1].ID = i;
Q[i - 1].d = 1.0 * p[i] / w[i];
P += p[i];
W += w[i];
}
if (W <= c)return P;
Sort(Q, n);
KnapK;
K.p = new Typep[n + 1];
K.w = new Typew[n + 1];
for (auto i = 1; i <= n; i++) {
K.p[i] = p[Q[i - 1].ID];
K.w[i] = w[Q[i - 1].ID];
}
K.cp = 0;
K.cw = 0;
K.c = c;
K.bestp = 0;
K.Backtrack(1);
delete[]Q;
delete[]K.w;
delete[]K.p;
return K.bestp;
}
#endif