完美运行的01背包问题程序

1、贪心算法： #include #define max 100 / 最多物品数 void sort (int n,float amax,float bmax) / 按价值密度排序 int j,h,k; float t1,t2,t3,cmax; for(k=0;kn;k+) ck=ak/bk; for(j=0;jn;j+) if(cjcj+1) t1=aj;aj=aj+1;aj+1=t1; t2=bj;bj=bj+1;bj+1=t2; t3=cj;cj=cj+1;cj+1=t3; void knapsack(int n,float limitw,float vmax,float wmax,int

2、xmax) float c1; /c1 为背包剩余可装载重量 int i; sort(n,v,w); / 物品按价值密度排序 c1=limitw; for(i=0;ic1)break; xi=1; xi为1时，物品i在解中 c1=c1-wi; void main() int n,i,xmax; float vmax,wmax,totalv=0,totalw=0,limitw; cout请输入 n 和 limitw:; cinn limitw; for(i=1;i=n;i+) xi=0; / 物品选择情况表初始化为 0 coutvv请依次输入物品的价值：e ndl; for(i=1;ivi; c

3、outendl; coutvv请依次输入物品的重量：vve ndl; for(i=1;iwi; 2 / 15 couxAend-八 knapsackp-imifwMWxx couxAThe se-eaon is= fo(iMAHnT+) 宀 OO / 求最小值函数 int min(int x,int y) return x= y ? y:x; void Knaspack() int Max=min(wn-1,W); for(int j=1; j = Max ; j+) Vnj=0; for(j=wn; j 1 ; i-) Max=min(wi-1,W); for( j=1; j = Max ;

4、 j+) Vij=Vi+1j; for( j=wi; j w1) V1W=max(V1W,V2W-w1+v1); / 生成向量数组，决定某一个物品是否应该放入背包 void Traceback() for(int i=1; i nW; coutvv输入每件商品的重量w:vendl; for(int i=1;iwi; memset(V,0,sizeof(V); coutvv输入每件商品的价值v:vvi; Knaspack();构造矩阵 Traceback(); /求出解的向量数组 int totalW=0; int totalV=0; / 显示可以放入的物品 coutvv所选择的商品如下:end

5、l; coutvv序号 i:重量 w:价格 V：vvendl; for(i=1; i = n ; i+) if(besti = 1) totalW+=wi; totalV+=vi; coutsetiosflags(ios:left)setw(5)i coutvv放入的物品重量总和是：vvtotalWvv totalV using namespace std; class Knap friend int Knapsack(int p,int w,int c,int n ); public: void print() for(int m=1;m=n;m+) coutbestxm ; coutend

6、l; ; private: int Bound(int i); void Backtrack(int i); int c;/ 背包容量 int n; / 物品数 int *w;/ 物品重量数组 int *p;/ 物品价值数组 int cw;/ 当前重量 int cp;/ 当前价值 int bestp;/ 当前最优值 int *bestx;/ 当前最优解 int *x;/ 当前解 ; int Knap:Bound(int i) / 计算上界 int cleft=c-cw;/ 剩余容量 int b=cp; / 以物品单位重量价值递减序装入物品 while(i=n b+=pi; i+; / 装满背包

7、 if(in) if(bestp WRW*1 (*V=T+Mg 七 宀 cn05 宀 -cbudls q sXHmxls q (+ruHvrL4UD04 class Object friend int Knapsack(int p,int w,int c,int n); public: int operator=a.d); private: int ID; float d; ; int Knapsack(int p,int w,int c,int n) / 为 Knap:Backtrack初始化 int W=0; int P=0; int i=1; Object *Q=new Objectn;

8、 for(i=1;i=n;i+) Qi-1.ID=i; Qi-1.d=1.0*pi/wi; P+=pi; W+=wi; if(W=c) return P;/ 装入所有物品 / 依物品单位重量排序 float f; for( i=0;in;i+) for(int j=i;jn;j+) if(Qi.dQj.d) f=Qi.d; Qi.d=Qj.d; Qj.d=f; Knap K; K.p = new intn+1; K.w = new intn+1; K.x = new intn+1; K.bestx = new intn+1; K.x0=0; K.bestx0=0; for( i=1;ic; coutvv请输入物品的个数(n)： n; p=new intn+1; w=new intn+1; p0=0; w0=0; coutvv请输入物品的价值(p)： endl; for(i=1;ipi; cout 请输入物品的重量