总结经典动态规划——01背包

题目描述

已知有n 个物品和一个承重为 content 的背包，物品 i 的重量以及价值分别为 weight[i]、 value[i] 。问：应如何选择装入背包的物品，使得装入背包中的物品的总价值最大？

众所周知，这题是动态规划的入门题。那么什么是动态规划？

我的理解是，当大问题难以解决时，先用求解小问题，然后后面求解大问题的时候我们就可以直接拿着小问题的结果来计算大问题。

对于01背包，大问题就是已知背包容量和物品的重量和价值，让你选择不止一个物品使得背包价值最大。

1. 背包容量小于当前物品重量

那直接让我选我哪知道怎么选嘛，所以我们将问题缩小，假设当前只有1个物品，已知其价值和重量。当背包容量很小时，甚至小于当前物品的重量，那现在你会选了吗？是不是显然装不了，就不选这个物品。引申一下，也就是考虑结果是不取当前物品i，那现在确定不选i号物品，是不是现在的背包中的价值就等于考虑完物品i-1背包中的价值？于是引出第一个递推公式：

前提是当背包容量小于当前物品重量：

：背包容量为j，有i个物品时，所能装入物品的最大价值

2. 背包容量不小于当前物品重量

既然背包容量大于物品重量，我们就一定要装当前的物品吗？答案是不一定能装当前物品，试想就算能装下，若这个物品却不那么之前，那我装了不是亏了吗，还占用背包空间。那什么时候一定能装入呢？综合之前装入背包的物品的情况分析，若装了此物品比不装此物品，背包中价值更大时才能装，引出第二个递推公式:

前提是当背包容量不小于当前物品重量：

：若把第i个物品装入背包，此时需要腾出的空间给第i个物品，背包剩余空间为，再加上背包容量只有时所能装入物品的最大价值，就是装入物品i所能获得的最大价值

给个的表格理解一下：

const vector<int> value = {0, 6, 3, 5, 4, 6}; // n = 5 种物品
const vector<int> weight = {0, 2, 2, 6, 5, 4}; //为方便写代码，vector长度为6，0号元素为0
const int content = 10; //背包承重      

1	2	3	4	5	6	7	8	9	10
1	6	6	6	6	6	6	6	6	6
2	6	6	9	9	9	9	9	9	9
3	6	6	9	9	9	9	11	11	14
4	6	6	9	9	9	10	11	13	14
5	6	6	9	9	12	12	15	15	15

填表顺序：从上到下，一次填一行，表示背包容量从小变大，物品由少变多

最优解：5个物品，容量为10， = 15

模拟填写表格的代码：

/**
 *  @author Leo
 *  递推公式：
 *  save[i][j] = save[i-1][j]   //   j < weight[i]
 *  save[i][j] = max(save[i-1][j-weight[i]] + value[i], save[i-1][j])  // j >= weight[i]
 */
vector<vector<int>> count(){
    int n = weight.size() - 1;
    vector<vector<int>> save;
    save.resize(n + 1); //行
    for (int i=0; i<save.size(); i++){
        save[i].resize(content + 1); //列
    }
    for (int i = 1; i <= n; i++){
        for(int j = 1; j <= content; j++){
            if(j >= weight[i]){
                save[i][j] = max(save[i-1][j-weight[i]] + value[i], save[i-1][j]);
            }else{
                save[i][j] = save[i-1][j];
            }
        }
    }
    return save;
}      

通过表格我们可以确定获得的最大价值，但是我们还不清楚具体选择哪几个物品。

接下来根据表格构造最优解：

构造一个 数组，表示不取，表示取。

vector<int> getSelection(vector<vector<int>> save){
    vector<int> select(save.size(), 0);
    int n = save.size() - 1;//n个物品
    int cur_c = save[0].size() - 1;//背包容量
    for(int i = n; i > 1; i--){
        if(save[i][cur_c] == save[i-1][cur_c]){
            select[i] = 0;
        }else{
            select[i] = 1;
            cur_c -= weight[i];
        }
    }
    select[1] = save[1][content] > 0 ? 1 : 0;
    return select;
}