(原创精品)0-1背包问题(回溯法).docVIP

0-1背包问题 0-1背包问题的解空间可用子集树表示 在有哪些信誉好的足球投注网站解空间树时，只要其左儿子结点是一个可行结点——有哪些信誉好的足球投注网站进入其左子树 当右子树中有可能包含最优解——进入右子树有哪些信誉好的足球投注网站 否则将右子树减去 r——当前剩余物品价值总和 cp——当前价值 bestp——当前最优价值 当cp+r≤bestp时，可减去右子树 计算右子树中解的上界的更好的方法 将剩余物品依其单位价值排序 依次装入物品，直至装不下时 再装入该物品的一部分而装满背包 由此得到的价值——右子树中解的上界 0-1背包问题的一个实例 Knap的数据成员记录解空间树中的结点信息 以减少参数传递及递归调用所需的栈空间 在解空间树的当前扩展结点处， 仅当要进入右子树时才计算上界Bound，以判断是否可将右子树减去 ④ 进入左子树时不需计算上界，因为其上界与其父结点的上界相同 核心代码： tempclass Typew,class Typep class Knap{ friend Typep Knapsack(Typep*,Typew*,Typew,int); private: Typep Bound(int i); Void Backtrack(int i); Typew* w; Typep* p; Typew cw; Typep cp; Typep bestp; }; Tempclass Typew, Type Typep void KnapTypew, Typep::Backtrack(int i) { if(in){ bestp=cp; return;} if(cw+w[i]=c){ cw+=w[i]; cp+=p[i]; Backtrack(i+1); cw-=w[i]; cp-=p[i]; } templateclass Typew, class Typep Typep KnapTypew, Typep::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]/w[i] * cleft; return b; }