beibao.rar_Knapsack machine _knapsack bound_knapsack branch_部分背包

#include #define n 4 double m=15; double w[]={2,4,6,9}; double p[]={10,10,12,18}; int x[n]; int x1[n]; double max=0; double totalweight=0; void solve(int i){ if(i==n){ int i;double sum; for(sum=0,i=0;i sum+=x1*p; if(sum>max){ max=sum; for(i=0;i x=x1; } return; } x1=0;/* 将x置为0 */ solve(i+1); if(totalweight+w<=m){ x1=1;/* 将x置为1 */ totalweight+=w; solve(i+1); totalweight-=w; } } int main(){ int i; solve(0); for(i=0;i printf("x%d=%d ",i+1,x); return 0; } /* 0/1背包问题的动态规划法算法*/ #include #include #define ymax 100 #define nmax 100 float f[nmax][ymax]; void Knapsack(float p[],int w[],int c,int n) { int y=0,i=0; for(y=0;y f[n][y]=0; for(y=w[n];y<=c;y++) f[n][y]=p[n]; for(i=n-1;i>1;i--) { for(y=0;y f[y]=f[i+1][y]; for(y=w;y<=c;y++) f[y]=(f[i+1][y]>(f[i+1][y-w]+p))?f[i+1][y]:(f[i+1][y-w]+p); } f[1][c]=f[2][c]; if(c>=w[1]) f[1][c]=(f[1][c]>(f[2][c-w[1]]+p[1]))?f[1][c]:(f[2][c-w[1]]+p[1]); } void traceback(int w[],int c,int n,int x[]) { int i=0; for(i=1;i if(f[c]==f[i+1][c]) x=0; else { x=1; c-=w; } x[n]=f[n][c]?1:0; } int main() { float s=0,temp=0; float *p; int m=0,n=0,i=0,*w,*x; printf("please input the maximum weight of the bag:nm="); scanf("%d",&m); printf("please input the number of objects:nn="); scanf("%d",&n); p=(float*)malloc((n+1)*sizeof(float)); printf("please input the prices of all the objects:n"); for(i=1;i<=n;i++) scanf("%f",p+i); w=(int*)malloc((n+1)*sizeof(int)); printf("please input the weight of all the objects:n"); for(i=1;i<=n;i++) scanf("%d",w+i); x=(int*)malloc((n+1)*sizeof(int)); Knapsack(p,w,m,n); traceback(w,m,n,x); s=f[1][m]; printf("the max value is %fn",s);/*输出*/ for(i=1;i<=n;i++) { if(x==1) { printf(" the p: %f",p); printf(" the w: %dn",w); } } return 0; }