2020-06-14 01背包问题

知识点：https://blog.csdn.net/achesong/article/details/88428895

#include <stdio.h>
#define N 6
#define M 21
#define W 20
int dp[N][M];
int w[N] = {0};
int v[N] = {0};
void knapsack(){
    int i, j;
    int value1, value2;
    for(i = 1; i < N; i++){ // 前i件物品
        for(j = 1; j < N; j++){ // 背包剩余空间
            if(w[i] > j){   // 第i件物品太重放不进去
                dp[i][j] = dp[i - 1][j];
            }   
            else{
                value1 = dp[i-1][j - w[i]] + v[i];  // 第i件物品放进去
                value2 = dp[i-1][j];    // 第i件物品不放进去
                dp[i][j] = max(value1, value2);
            }
        }   
    }
}
int main(){
    knapsack();
    printf("%d\n", dp[5][20]);      // 5件物品，背包容量为20，最多可以放的价值
    return 0;
}