啊w 01背包呐～给出一堆不可拆分的东西，它们有各自的重量和对你来说相应的价值，但是你的背包能装的最大重量是有限的，这个时候要如何选择装哪些东西使得背包里的东西有着最大的总价值呢～
贪心算法
第一种想法则是分别计算出每样东西的单位重量的价值，然后按照降序排序，最后在背包能放的前提下，取单位重量的价值最大的那一件放进去即可w
这种想法则是贪心算法，但是遗憾的是，贪心算法在每件物品不可分的条件下，它不能总是保证背包里的东西有着最大的总价值。例如物品的情况如下表
| 物品i | 重量 | 价值 | 单位重量的价值 |
|---|---|---|---|
| 1 | 10 | 60 | 6 |
| 2 | 20 | 100 | 5 |
| 3 | 30 | 120 | 4 |
而背包最大能装下50重量，在这种情况下，按照贪心算法的话，我们会拿A和B，也就是总价值为160～
但是我们稍稍计算一下就知道实际上选择B和C才能使背包里的东西有着最大的总价值，也就是220 www
使用贪心算法求解并不难～按照上面的思路来写就好
#!/usr/bin/env python3 # -*- coding:utf-8 -*- import numpy as np def greedy(value, weight, capacity): """ 0/1 backpack - Greedy """ # 计算每件物品单位重量的价值 # 为了方便 我们把该物品原始的下标也放进其对应的结果里 ratio = [[i, value[i]/weight[i]] for i in range(len(value))] # 按照单位重量的价值降序排序 ratio = sorted(ratio, key=lambda x: x[1], reverse=True) # 一开始的总价值为 0 value = 0 # 一开始都没有放进背包 choose = np.zeros(len(value)) for i in range(len(value)): # 获取排序之后 某物体的原始下标 index = int(ratio[i][0]) # 如果背包能装下该物品 if capacity - weight[index] >= 0: # 装进去～ # 容量减少 capacity -= weight[index] # 价值增加 value += value[index] # 标记该物品被装进了背包 choose[index] = 1 # 返回最后的总价值、有哪些物品被装进去 return (value, choose) # 每件物品的价值 value = [60, 100, 120] # 每件物品的重量 weight = [10, 20, 30] # 背包最大承受的重量 capacity = 50 print(greedy(value, weight, capacity))
穷举算法
那么贪心既然不好用的话，我们就多试试各种组合？也就是穷举所有的可能性w
其实题目的话——01背包——也在暗示我们可以用二进制来表示对这些物品的取舍情况，有 n 个物品的话，就用 n 个 bit 的二进制位就好～
蓝后既然又是二进制的话，每次给那个 n 个 bit 的二进制数 +1 就可以对应一种情况了～随后按照二进制位的 0/1 来判断，找出最大的那一种赋值就好www～
#!/usr/bin/env python3 # -*- coding:utf-8 -*- def bruteforce(value, weight, capacity): """ 0/1 backpack - Bruteforce """ # 最大的价值 maxv = -1 # 最大价值所对应的那组选择 max_group = -1 # 从 0b0 到 0b11..11 (共 len(value) 个 1) for i in range(2**len(value)): # 当前选择的容量 current_w = 0 # 当前选择的价值 current_v = 0 # 对应到二进制上 for b in range(len(value)): if (i >> b) & 1: # 如果还能装下 if current_v + value[b] >= capacity: # 继续计算 current_w += weight[b] current_v += value[b] else: # 否则这组之后的都不用算了 break # 如果这组的价值比之前的大 if current_v > maxv: # 更新 maxv = current_v max_group = i # 返回最大价值和选择 return (maxv, bin(max_group)[2:]) # 每件物品的价值 value = [60, 100, 120] # 每件物品的重量 weight = [10, 20, 30] # 背包最大承受的重量 capacity = 50 print(bruteforce(value, weight, capacity))
虽然穷举法可以保证我们找到最优解，但是其复杂度是$O(2^n)$的，物品数量每增加1，计算量就要翻倍∑(ﾟДﾟ)
动态规划
那。。。聪明一点的方法有么～是有的ω
动态规划(Dynamic Programming)的方法就可以做到～
#!/usr/bin/env python3 # -*- coding:utf-8 -*- import numpy as np def dp(value, weight, capacity): """ 0/1 backpack - Dynamic Programming """ # 初始化我们的memo~ memo = np.zeros((len(value) + 1, capacity + 1)) # 开始填表w # 首先 i 是迭代每一件物品～ for i in range(0, len(value)): # 然后是每一种可能的背包剩余重量 # 这里简化代码，从 [0, capacity] 的每一个数都考虑了 # 要优化的话，可以从这里下手～ for j in range(0, capacity + 1): # 在不选择第 i 件物品时，无论剩余承重 j 是多少 # 背包的装的物品的总价值都不会变 memo[i][j] = memo[i - 1][j] # 如果剩余容量 j 可以让窝们考虑选不选的话 if j >= weight[i]: # 那么跟窝们之前说的一样 memo[i][j - weight[i]] = max([memo[i-1][j]+ value[i], memo[i - 1][j - weight[i]]]) # 最后返回在有 n 件物品时，剩余容量为 0 时的值就可以了 return memo[len(value) - 1][0] # 每件物品的价值 value = [60, 100, 120] # 每件物品的重量 weight = [10, 20, 30] # 背包最大承受的重量 capacity = 50 print(dp(value, weight, capacity))
回溯法
除了动态规划之外，我们还有回溯法～和解决N皇后问题的时候类似～
#include <iostream> #include <map> #include <vector> using namespace std; /* 输入～ 第一行是指有 n 件物品 接下来从第二行起、连续 n 行是这些物品 第一个数是 weight，第二个数是 value 整个输入的最后一行是背包最大可以装的重量w 5 2 6 2 3 6 5 5 4 4 6 10 */ struct object { int weight; int value; }; /** * 01背包w * * @param capacity 当前背包还能装多少 * @param value 当前背包里东西的总价值 * @param i 当前考虑的是下标为 i 的物品是否要放进去 * @param objects 所有的物品 * @param take_it_or_not 记录第 i 件物品是否要当进去 */ pair<int, vector<bool>> backpack(int capacity, int value, int i, const vector<object *> &objects, vector<bool> take_it_or_not) { // 我们有米有下标为 i 的物品 if (i >= objects.size()) { // 如果没有就返回当前价值 return pair<int, vector<bool>>{value, take_it_or_not}; } // 有的话，就拿出下标为 i 的物品 object * current_obj = objects[i]; // 不管背包还能不能装 // 对于这一件物品，我们都*可以*选择不去装它 pair<int, vector<bool>> not_take_i = backpack(capacity, value, i + 1, objects, take_it_or_not); // 如果装不下这件物品的话 if (current_obj->weight > capacity) { // 我们就直接返回不去装它的结果w return not_take_i; } // 如果还可以装下这件物品的话 // 我们就继续看看变化之后（容量减少、价值增加）背包的情况 pair<int, vector<bool>> take_i = backpack(capacity - current_obj->weight, value + current_obj->value, i + 1, objects, take_it_or_not); // 比较拿/不拿着一件物品 if (not_take_i < take_i) { // 拿上它的价值更多 // 那就记下～ take_i.second[i] = true; return take_i; } else { // 否则就不拿这一件w not_take_i.second[i] = false; return not_take_i; } } int main(int argc, const char * argv[]) { int n; cin >> n; vector<object *> objects; // 依次输入 n 件物品 while (n--) { object * obj = new object(); // 第一个数是 weight，第二个数是 value cin >> obj->weight >> obj-> value; // 放进数组里～ objects.push_back(obj); } // 记录某一件物品是否要装进背包 vector<bool> take_it_or_not; // 预先调整好大小 take_it_or_not.resize(objects.size()); // 输入背包的最大重量 int capacity; cin >> capacity; // 开始尝试吧w pair<int, vector<bool>> maximum = backpack(capacity, 0, 0, objects, take_it_or_not); printf("maximum: %d\n", maximum.first); for (int i = 0; i < maximum.second.size(); i++) { printf("%d: %s\n", i, maximum.second[i] ? "YES" : "NO"); } }