01背包问题

01背包问题是最经典的背包问题，给定几个物品的价值和体积，给定背包容量，求解背包价值最值。

基础思想是构造一个动态规划数组，下标 i 表示可容纳的体积，值代表剩余 i 体积时，最大可存储的物品价值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<algorithm>

int f[100] = {0}, v[100], w[100];
int main(){
    int m, n;
    std::cin >> n >> m;
    for(int i = 1; i <= n; i++){
        std::cin >> v[i] >> w[i];
    }

    for(int i = 1; i <= n; i++){
        for(int j = m; j >= v[i]; j--){
            f[j] = std::max(f[j], f[j - v[i]] + w[i]);
        }
    }
    std::cout << f[m];

    return 0;
}

分析一下核心代码： 

1
2
3
4
5
for(int i = 1; i <= n; i++){
    for(int j = m; j >= v[i]; j--){
        f[j] = std::max(f[j], f[j - v[i]] + w[i]);
    }
}

从最大剩余容量m（j=m）开始，向前查找，看放入一个w[ i ]后，f的总价值是否变大。第一个物品，第二个物品依次放入。。。

完全背包问题

在01背包问题的基础，加上条件：任何物品个数无限

1
2
3
4
5
6
7

for(int i = 0; i < n; i++){
	std::cin >> v >> w;
    for(int j = v; j <= m; j++){
        f[j] = std::max(f[j], f[j - v] + w);
    }
}

和01背包的代码块不一样的地方在于，这里的内层循环是从小到大的，这样做的目的是，使得一个物品可以被放入多次。

举个例子，现在有物品2 5，在j = 2时，f[j] = f[0] + 5 = 5，当j = 4时，f[j] = f[2] + 5 = 10也是存在的，自然而然满足了完全背包问题的附加条件。

回来看01背包问题时的内层循环，同样是物品2 5，假如m（背包容量）为4，j = 4时，f[j] = f[2] + 5 = 5，当j = 2时，f[j] = f[0] + 2 = 5，可见f[4] = f[2] 都为5，一个物品无法在一轮循环中被放入多次。

正常来说，完全背包问题中，放入物品体积不超过容量；假设题目条件是放入物品体积要恰好为容量，只需把除了f[0] 以外的 f[j] 都初始化为负无穷。

多重背包问题

本质上还是01背包问题，加上条件：给定物品的个数。

只需要在01背包的基础上，再加上一层循环，来检查一次放入k个物品时，f[j] 是否会变大。

和完全背包不同的是，多重背包问题的个数有限制，因此不能通过内层循环从小到大来实现：完全背包实现的是一次放一个物品，但是可以放多次；而多重背包在code时的思想时，一个物品放一次，但是可以一次性放多个（由一层循环限制）

1
2
3
4
5
6
7
8
9
10
for(int i = 0; i < n; i++){
    std::cin >> v >> w >> s;
    for(int j = m; j >= 0; j--){
        //这里j >= 0不影响，下面还有一层判读
        for(int k = 1; k <= s && k * v <= j; k++){
            //k代表放入物品个数
     		f[j] = std::max(f[j], f[j - k * v] + k * w);          
		}
    }
}

01展开优化

可以将多重背包问题看成01背包问题来解决，把物品的个数展开，每个都是01背包的一种输入。

展开亦有技巧，用二进制方式展开能最大程度的节省资源，假如s为8，展开为1 4 2 1，受到二进制01思想的启发，在这种展开方式中，通过特定的组合，能完全表示数字1到8。

设置一个objects结构以及对应容器vector，用来存放体积与价值。

展开方式如下：

1
2
3
4
5
6
7
for(int k = 1; k <= s; k *= 2){
	s -= k;
    objects.emplace_back(v * k, w * k);
}
if(s > 0){
	objects.emplace(v * s, w * s);
}

分组背包问题

多重背包问题是分组背包问题的一种特殊情况。

分组背包问题就是，将某些物品分到一组，一组中最多选一个物品。

为什么说多重背包问题是分组的特殊情况呢？

假设将分组看多重背包的各种情况，例如4个a物品，看成分组背包中的a，2a，3a，4a四种价值的物品，仅能取其中之一。于是乎，我们就可以用多重背包的一般思想来解决分组背包问题。

假设分组背包中有4个物品，abcd，类似于多重背包中的，a2a3a4a，一样的解决思路，每组物品中的物品间没有倍数关系了而已。所以我们可以用多重背包的一般思想解决分组背包问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i = 0; i < n; i++){
    std::cin >> s;
    for(int j = 0; j < s; j++){
     	//分组读取数据
        std::cin >> v[j] >> v[j];
    }
    for(int j = m; j >= 0; j--){        
        for(int k = 0; k < s && v[k] < j; k++){      
            //对比多重背包k*w用w[k]代替，k*v用v[k]代替
     		f[j] = std::max(f[j], f[j - v[k]] + w[k]);          
		}
    }
}