用动态规划法求解0/1背包问题

#include "DKnapsack.h" #include <queue> using namespace std; const float epsilon = 0; //构造方法传递参数 CDynKnapsack::CDynKnapsack(int nNum,float nCapacity,float *nWeight,float *nProfit) { n = nNum; //物品数目 m = nCapacity; //背包容量 w = nWeight; //各物品重量 p = nProfit; //各物品效益 } CDynKnapsack::CDynKnapsack(float *prof,float *wei,float mm,int len) { n = len; //物品数目 m = mm; //背包容量 w = wei; //各物品重量 p = prof; //各物品效益 } //在S(i-1)中求使得point[u].X+w[i]不超过背包载重的最大下标u int CDynKnapsack::GetMaxValueU(int low,int high,int i) { int u = low-1; //赋初值 for(int j=low; j<=high; j++) { float ww = point[j].X+w[i]; if(ww <= m) //如果小于等于背包容量则将其下标赋给u u = j; } //返回最大下标u return u; } //从S(0)开始计算所有S(i),并保存point和mark的值及返回最大效益值 float CDynKnapsack::GetOfSandMaxProfit() { float ww,pp; int next; //始终指示数组point中的下一个空的位置 mark[0] = 0; //赋初值 //求S(0) point[0].X = point[0].P = 0.0; //point[0].P = 0.0; point[1].X = w[0]; point[1].P = p[0]; //S(0)的起始位置 int low = 0; int high = 1; //next = 2; mark[1] = next = 2; //数组point的下一个空闲位置 for (int i=1; i<=n-1; i++) { int k = low; //调用GetMaxValueU获取使得point[u].X+w[i]不超过背包载重的最大下标u int u = GetMaxValueU(low,high,i); //从S(i-1)生成S（1_i)，并合并成S(i) for(int j=low; j<=u; j++) { //生成S（1_i)中的一个阶跃点(ww,pp) ww = point[j].X+w[i]; pp = point[j].P+p[i]; //复制S(i-1)中的部分阶跃点到s(i)中 while ((k <= high) && (point[k].X < ww)) { point[next].X = point[k].X; point[next++].P = point[k++].P; } if ((k <= high) && (point[k].X == ww)) if (pp < point[k].P) pp = point[k++].P; //若(ww,pp)不被支配，则加入S(i)中 if (pp > point[next-1].P) { point[next].X = ww; point[next++].P = pp; } //舍弃所有被支配的阶跃点 while ((k <= high) && (point[k].P <= point[next-1].P)) k++; } //复制S(i-1)中剩余的阶跃点到s(i)中 while (k <= high) { point[next].X = point[k].X; point[next++].P = point[k++].P; } //S(i+1)初始化 low = high+1; high = next-1; mark[i+1] = next; } return point[next-1].P; //返回求得的最大效益值 } //由保存的point和mark回溯求问题的最优解向量 void CDynKnapsack::TraceBack(int *x) { //初始化为当前空闲位置的前一个位置 float ww = point[mark[n]-1].X; //回溯求解向量 for (int j=n-1; j>0; j--) { x[j] = 1; //假设(X[n-1],P[n-1])属于S(1_n-1) //如果(X[n-1],P[n-1])属于S(n-2)则X[n-1]=0 for (int k=mark[j-1]; k<mark[j]; k++) if (ww == point[k].X) x[j] = 0; //如果x[j]==1则减掉w[j]后继续循环 if (x[j]) ww = ww-w[j]; } //最后一对序偶 if (ww==0) x[0] = 0; else x[0] = 1; } void CDynKnapsack::LUBound(float cp,float cw,int k,float &LBB,float &UBB) { LBB = cp; float c = cw; for (int i=k; i<n; i++) { if (c < w[i]) { UBB = LBB + c*p[i]/w[i]; for (int j=i+1; j<n; j++) { if (c >= w[j]) { c = c-w[j]; LBB = LBB+p[i]; } } return; } c = c-w[i]; LBB = LBB+p[i]; } UBB = LBB; } float CDynKnapsack::LCBB() { Node *child,*E; float LBB,UBB,L; ans = NULL; queue<pqNode> pq;//(N); root = new Node(NULL,false); E = root; LUBound(0,m,0,LBB,UBB); pqNode e(m,0,UBB,0,root); L = LBB - epsilon; do { int k = e.level; float cap = e.cu; float prof = e.profit; E = e.ptr; if ((k == n) && (prof > L)) { L = prof; ans = E; } else { if (cap >= w[k]) { child = new Node(E,true); e.ptr = child; e.level = k+1; e.cu = cap - w[k]; e.profit = prof + p[k]; pq.push(e); } LUBound(prof,cap,k+1,LBB,UBB); if (UBB > L) { child = new Node(E,false); e.ptr = child; e.level = k+1; e.cu = cap; e.profit = prof; e.UBB = UBB; pq.push(e); if (L < LBB - epsilon) L = LBB-epsilon; } } if (pq.empty()) return 0; pq.pop(); }while (e.UBB > L); return L; }