#include <stdio.h>

#define N 4 // 物品数量
#define W 5 // 背包容量

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int v[] = {0, 2, 4, 5, 6}; // 物品价值数组
    int w[] = {0, 1, 2, 3, 4}; // 物品重量数组

    int f[N + 1][W + 1] = {}; // 子问题解数组

    int i, j;
    for (i = 1; i <= N; i ++ ) {
        for (j = 1; j <= W; j ++ ) {
            f[i][j] = f[i - 1][j]; // 默认不选第 i 个物品

            if (j >= w[i]) { // 选第 i 个物品的前提条件
                // 等于 不选第 i 个物品 和 选第 i 个物品 两者的较大值
                f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);
            }

            // 上方是写法 1
            /* ============================================================ */
            // 下方是写法 2 

            /*
            if (j >= w[i]) { // 选第 i 个物品的前提条件
                // 等于 不选第 i 个物品 和 选第 i 个物品 两者的较大值
                f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
            } else { // 不选第 i 个物品
                f[i][j] = f[i - 1][j]; // 等于 从前 i - 1 个物品中选，背包容量为 j 时的最大价值
            }
            */
        }
    }

    printf("%d\n", f[N][W]);

    for (i = 0; i <= N; i ++ ) {
        for (j = 0; j <= W; j ++ ) {
            printf("%d ", f[i][j]);
        }
        printf("\n");
    }

    return 0;
}