C语言解决背包问题

1、首先打开VC++6.0

3、选择C++ source file 新建一个空白文档

5、写一个函数，用来得到多个最优解void knapsack(int v[NUM],int w[NUM],int c,int m[NUM ][CONTENT]){ int n=NUM-1; int i,j; int jMax; if((w[n]-1)< c)jMax = w[n]-1; elsejMax = c; /* 初始化m[n][j] */ for(j = 0; j <= jMax; j++)m[n][j] = 0; for(j = jMax +1; j <= c; j++)m[n][j] = v[n]; /*使用非递归的算法来求解m[i][j] */ for(i = n-1; i > 0; i--) { if((w[i]-1)< c) jMax = w[i]-1; else jMax = c; for(j = 0; j <= jMax; j++) m[i][j] = m[i+1][j] ; for(j = jMax +1; j <= c; j++) { if(m[i+1][j] >= (m[i+1][j-w[i]]+v[i])) m[i][j] = m[i+1][j] ; elsem[i][j] = m[i+1][j-w[i]]+v[i];} } if(c>w[0]) { if(m[1][c] >= (m[1][c-w[0]]+v[0])) m[0][c]= m[1][c]; elsem[0][c]= m[1][c-w[0]]+v[0]; } else m[0][c]= m[1][c];}

7、写个函数，用来输出最优解void printResult(int flag[NUM],int w[NUM],int v[NUM],int m[NUM][CONTENT]){int i;printf("the knapsack should contain:\n");printf(" num weight value \n");for(i = 0;i < NUM; i++){if(flag[i] == 1) printf(" %d %d %d\n",i,w[i],v[i]);}printf("the max value in the knapsack is: %d\n",m[0][CONTENT]);}

9、运行结果