#include <stdio.h>
#define N 4
#define W 5
int max(int a, int b){
return a > b ? a : b;
}
int main () {
printf("算法-动态规划-01背包问题! - c.jsrun.net.\n");
int i,j;
int v[] = {0, 2, 4, 5, 6};
int w[] = {0, 1, 2, 3, 4};
int f[N + 1][W + 1] = {};
printf("物品编号\t1\t2\t3\t4\n物品价值\t2\t4\t5\t6\n物品重量\t1\t2\t3\t4\n--------\n");
printf("容量j=\t0\t1\t2\t3\t4\t5\n");
printf("重量i=0\t0\t0\t0\t0\t0\t0\n");
for(i = 1; i <= N; i ++){
printf("重量i=%d\t0", i);
for(j = 1; j <= W; j++){
f[i][j] = f[i-1][j];
if(j >= w[i]){
f[i][j] = max(f[i][j], f[i-1][j-w[i]] + v[i]);
}
printf("\t%d", f[i][j]);
}
printf("\n");
}
printf("--------\n最优解=%d", f[N][W]);
return 0;
}