#include <stdio.h> #include <stdlib.h> #define random(x) (rand()%x)+1 //产生随机数 (0,100] #define N 5 //物品规模 #define C 6 //背包容量 int x[N]; //解向量 int max(int a,int b){ return a>b?a:b; } int min(int a,int b){ return a<b?a:b; } //输出解向量 void printx(int x[],int n){ printf("解向量x={"); for(int i=0;i<n-1;i++){ printf("%d,",x[i]); } printf("%d}\n",x[n-1]); } void dynamicProgramming(int w[],int v[],int x[],int n,int c,int m[][C+1]){ int jMax=min(w[n-1]-1,c); for(int j=0;j<=jMax;j++) m[n-1][j]=0;//第n个物品不能放入容量j不够的包里 for(int j=w[n-1];j<=c;j++) m[n-1][j]=v[n-1];//第n个物品能放入容量为j的背包 for(int i=n-2;i>=0;i--){ jMax=min(w[i]-1,c); for(int j=0;j<=jMax;j++) m[i][j]=m[i+1][j];//容量不够,所以都不放入 for(int j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);//放和不放比较,如果最大价值能增加就放,否则不放 } m[0][c]=m[1][c]; if(c>=w[0]) m[0][c]=max(m[0][c],m[1][c-w[0]]+v[0]); //打印数组m printf("m数组如下所示:\n"); for(int i=0;i<n;i++){ for(int j=0;j<C+1;j++){ printf("%7d",m[i][j]); } printf("\n"); } //由二维数组m构造最优解 for(int i=0;i<n-1;i++){ if(m[i][c]==m[i+1][c]) x[i]=0; else {x[i]=1;c=c-w[i];} } x[n-1]=(m[n-1][c])?1:0; } void main(){ //用数组初始化物品节点,背包容量为总重量的一半 int v[N]={5,4,3,6,8}; //价值数组 int w[N]={2,1,3,2,4}; //重量数组 int c=0; int m[N][C+1]; dynamicProgramming(w,v,x,N,C,m); printx(x,N); }