01背包小记

发布于 2019-01-23  287 次阅读


感谢太阳大佬的讲解

0-1背包是一个经典的DP问题(主要是OI考)

定义

有N件物品和一个容量为V 的背包。放入第i件物品耗费的背包容量是W[i],得到的价值是C[i]。求将哪些物品装入背包可使价值总和最大,而每件物品只有一个,可以选择不放。

0-1背包是其他背包问题的基础

无优化版本

我们用一个数组 f[i][v]来表示这个虚拟的背包,表示前i件物品恰放入一个容量为v的背包可 以获得的最大价值。

对于每一种物品,我们可以选或者不选,不选的话呢一切状态不变,选的话呢,则背包的容量减去W[i],背包里的物品价值加上C[i]。

于是我们可得到它的状态转移方程:

F[ⅈ][v]=max⁡(F[ⅈ−1][v],F[ⅈ−1][v−W[ⅈ]]+C[ⅈ])

这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生 出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v的背包 中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化 为一个只和前i−1件物品相关的问题。如果不放第i件物品,那么问题就转化 为“前i−1件物品放入容量为v的背包中”,价值为F[i−1,v];如果放第i件物 品,那么问题就转化为“前i−1件物品放入剩下的容量为v −Wi的背包中”, 此时能获得的最大价值就是F[i−1,v −Wi]再加上通过放入第i件物品获得的价 值Ci。——《背包九讲》

//code by extmool
#include <iostream>

#define V 500   //可以用 const int V=500 来代替

using namespace std;

int weight[20 + 1];
int value[20 + 1];
int f[20 + 1][V + 1];

int main() {
    int n, m;
    cout << "请输入物品个数:";
    cin >> n;
    cout << "请分别输入" << n << "个物品的重量和价值:" << endl; 
    for (int i = 1; i <= n; i++) {
        cin >> weight[i] >> value[i];
    }
    cout << "请输入背包容量:";
    cin >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (weight[i] > j) {
                f[i][j] = f[i - 1][j];
            }
            else {
                f[i][j] = f[i - 1][j] > f[i - 1][j - weight[i]] + value[i] ? f[i - 1][j] : f[i - 1][j - weight[i]] + value[i];
            }
        }
    }    
    cout << "背包能放的最大价值为:" << f[n][m] << endl; //输出最大价值
}

空间优化(重点)

我们压缩一下数组,方程就变成了这样

F[v]=max⁡(F[v],F[v - W[ⅈ]] + C[ⅈ])

但是第二重循环要逆序

为什么可以逆序?
因为我们如果正序循环修改了1个数的话,后面可能会用该数进行2次辨断,这样可能会多选几次。

懒得敲代码了

//code by extmool
#include <iostream>
#define V 500
using namespace std;
int weight[20 + 1];
int value[20 + 1];
int f[V + 1];
int main() {
    int n, m;
    cout << "请输入物品个数:";
    cin >> n;
    cout << "请分别输入" << n << "个物品的重量和价值:" << endl; 
    for (int i = 1; i <= n; i++) {
        cin >> weight[i] >> value[i];
    }
    cout << "请输入背包容量:";
    cin >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= 1; j--) {
            if (weight[i] <= j) {
                f[j] = f[j] > f[j - weight[i]] + value[i] ? f[j] : f[j - weight[i]] + value[i];
            }
        }
    }
    cout << "背包能放的最大价值为:" << f[m] << endl;
}

后记

时间仓促,如有bug请大佬指出,Thanks %%%

至于正序会怎么样? 秒变完全背包