编辑代码

#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");
    //当物品数量、背包容量 都为 0 时,价值也为 0;故 第一行、第一列 都为 0
    printf("重量i=0\t0\t0\t0\t0\t0\t0\n");
    for(i = 1; i <= N; i ++){//物品重量,从1-4
        printf("重量i=%d\t0", i);
        for(j = 1; j <= W; j++){
            f[i][j] = f[i-1][j];//默认最大价值 = 表[重量为i-1、容量为j]的价值
            if(j >= w[i]){//当 容量为j 大于等于 重量为i
                //最大值( 表[重量为i-1、容量为j]的价值, [重量为i]的价值 + 表[重量为i-1、容量为(容量j-重量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;
}