实验二、0-1背包问题（动态规划） 实验代码： #include int m[20][20]; int min(int w, int c) { int temp; if (w < c) temp = w; else temp = c; return temp; } int max(int w, int c) { int temp; if (w > c) temp = w; else temp = c; return temp; } void knapsack(int v[], int w[], int c, int n) { int jmax = min(w[n]-1, c); for (int j = 0; j <= jmax; j++) m[n][j] = 0; for (int k= w[n]; k<= c; k++) m[n][k] = v[n]; for(int i = n-1; i > 1; i--) { jmax = min(w[i]-1, c); for(int j = 0; j <= jmax; j++) m[i][j] = m[i+1][j]; for(int k = w[i]; k <= c; k++) m[i][k] = max(m[i+1][k], m[i+1][k-w[i]]+v[i]); } m[1][c] = m[2][c]; if(c >= w[1]) m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]); } void traceback(int x[], int w[], int c, int n) { for(int i = 1; i < n; i++) { 1 / 2 if(m[i][c] == m[i+1][c]) x[i] = 0; else { x[i]=1; c-= w[i]; } } x[n]=(m[n][c])?1:0; } void main() { int n=20,v[20],w[20],c=19,n=20,x[150]; for(int l=0;l<150,l++) x[l]=0; for(int i=0;i<20;i++) {v[i]=i; w[i]=20-i; } knapsack (v, w, c, n); traceback(x, w, c, n); for(int j=0;j<=20;j++) { printf("0为不装包，1为装包: %d\n",x[j]); } 测试结果截图为： 2 / 2 本文来源：https://www.wddqw.com/doc/12d6cdec81c758f5f61f670f.html