#include<stdio.h>
#include<math.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 ++){

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

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