01背包——动态规划

建立一个二维数组去记录最好的结果（把一个问题分为小的问题，求出小的问题最优解——一步一步的得出最终问题的最优解）

#include <stdio.h>

#define N 6  // 背包空间

// 物品
#define W 4  // 物品数量
int value[] = {7,3,5,2};   // 价值
int weight[] = {1,2,5,4};    // 重量

// 数组记录
int count[W+1][N+1] = {0};

void printResult(){
    int n,m;  // 两个for循环
    // 打印结果
    for(n=0; n<W+1; n++){
        for(m=0; m<N+1; m++){
            printf("%d ",count[n][m]);
        }
        printf("\n");
    }
}

void getBagResult(){
    int i,j;  // 两个for循环
    for(i=1; i<=W; i++){    // 遍历所有物品
        int nowWeight = weight[i-1];  // 当前物品的重量
        int nowValue = value[i-1];   // 当前价值
        for(j=1; j<=N; j++){   // 遍历从 1 - 10重量的情况
            // 如果可以加上当前物品——并且——加上后的价值大于之前记录的价值，则更新——不行则记录之前的！
            if(nowWeight<=j && nowValue + count[i-1][j-nowWeight] > count[i-1][j]){
                count[i][j] = nowValue + count[i-1][j-nowWeight];
            }else{
                count[i][j] = count[i-1][j];
            }
        }
    }
}

int main(){
    getBagResult();
    printResult();
    return 0;
}