目录
1. 问题引入
---> 1.1 找零钱问题
---> 1.2 动态规划
2. 背包问题描述及详解
---> 2.1 01背包及代码实现
---> 2.2 分数背包（Fractional Knapsack）及代码实现
问题引入
在介绍背包问题之前，我们先来看一个小问题：找零钱问题。
找零钱问题
背包问题的一个浅显版本是找零钱问题。描述如下[1]：
如果某人欠了我们43.68美元，结果他还给我们了一张100美元，你手里的钱从100美元到1美分数量不等，这时候你要怎么找给他？怎么拿纸币给他比较合适？
实现代码（Python 3）
#!/usr/bin/env pypy3
# -*- coding: utf-8 -*-
_all = [10000, 5000, 2000, 1000, 500, 200, 100, 50, 25, 10, 5, 1] # 这里以美分为单位。1美元 = 100美分
owed = 10000 - 4368 # 转换成分单位之后就行
payed = list() # 在payed数组中存储换币的单位
for i in _all: # 从最大的币值开始遍历
while (owed >= i):
owed -= i # 从大到小找钱
payed.append(i) # 找的钱放到payed数组中
if __name__ == "__main__":
print(payed)
print(sum(payed))
C++实现
#include <cstdio>
#include <vector>
using namespace std;
int main(void){
int _all [] = {10000, 5000, 2000, 1000, 500, 200, 100, 50, 25, 10, 5, 1}; // 这里以美分为单位
int owed = 10000 - 4368; // = 5632
vector<int> payed; // 初始化一个空向量
int sum_; // 定义后面的和
for(auto it: _all){ // 遍历数组
while (owed >= it){
owed -= it;
payed.push_back(it)
}
}
for (int i = 0; i <size(payed); i++){
printf("%d", payed[i]);
sum_ += payed[i];
}
printf("\n");
printf("%d", sum_);
return 0;
}
动态规划
在正式讲背包问题前，先要熟悉一下动态规划的概念。
由于递归会导致大量的重复计算，所以是否可以有一种方式对其进行优化呢？答案就是动态规划。动态规划的要旨是不要重复计算自己，换句话说，将已经计算的结果存储起来，以日后需要的时候不用再重复调用。
这样一来，算法复杂度便从指数级降到了线性级。
下面以Fibonicci数列的两种解法为例：
法一：递归
Python实现：
#!/usr/bin/env pypy3
# -*- coding: utf-8 -*-
def fib(n):
if (n <= 1):
return n
else:
return fib(n-2) + fib (n-1)
C/C++实现
#include <cstdio>
using namespace std;
int fib(int n){
if (n <= 1){
return n;
}
else{
f = fib(n - 2) + fib(n - 1);
return f;
}
}
法二：DP
Python实现：
#!/usr/bin/env pypy3
# -*- coding: utf-8 -*-
def fib(n):
f = [0 for i in range(n+1)]
# 由于是用Python写代码，无法像C/C++那样预先指定数组大小
# 所以先造一个全为0，大小为n的数组f存每次计算后的结果
# 造出数组后就不需要重复计算了
f[0] = 0
f[1] = 1
for i in range(n+1):
f[i] = f[i - 1] + f[i - 2]
return f[n]
C/C++实现
#include <cstdio>
#include <array>
using namespace std;
int f[100000]; // 指定一个足够大的数组
int fib(int n){
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= n; i++){
f[i] = f[i - 2] + f[i - 1];
}
return f[n];
}
背包问题描述及详解
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
这是一个经典的动态规划问题。一般将背包问题分为这么几种：01背包问题、分数背包问题、完全背包问题、多重背包问题。下面分别讨论。
01背包
01背包问题是背包问题中的基础。它的特点是：每种物品只有一件，可以选择放与不放。用比较抽象的语言表示是，有n件物品，每件物品的重量是w，价值为v，背包的容量为W。
根据如上信息，我们可以得到需要的变量如下：
| 变量名 | 类型 | 大小 | 作用 |
|---|---|---|---|
| n | int | 依实际情况而定 | 物品数 |
| c | int | 依实际情况而定 | 背包容量 |
| w | int array | n | 每个物品的重量 |
| v | int array | n | 每个物品的价值 |
根据动态规划的思想，我们可以把问题拆成一个一个子集来解决。试想，是不是可以考虑拆成背包重量为[1, W]的子集呢（思路1）？换成大白话说，就是是不是可以考虑为如果背包重量为1时，能达到的最大价值是多少？如果背包重量为2时，能达到的最大价值是多少？如果背包重量为3呢？
有了上面的考虑方法后，我们还应该想想是不是可以从另一个角度再考虑一下？
另一个考虑问题的角度是，“将前i件物品放入容量为v的背包中”（思路2）。如果只考虑前i件物品，那么，根据动态规划又可以转化为“将前i - 1件物品放入背包中”。第i件物品的策略可以是放或不放。如果不放，问题则转化为“将前i - 1件物品放入容量为v的背包中”；如果放，问题转化为“前i-1件物品放入剩下的容量为v-w[i]的背包中”。写成状态转移方程，则是：
m[i][j] = max(m[i - 1][j], m[i - 1][j - w(i)] + v[i])
"""
说明：
- i : 思路2中第i个物品
- j : 思路1中背包重量
- m: Memoisation集合
"""
上式的意思是：前i个东西放进容量为j的背包中，能获得的最大价值是多少？是不放第i个物品呢，还是放第二个物品呢？
有了如上思路后，我们可以写代码如下（用c++实现）：
//#include <bits/stdc++.h> //万能头文件
#include <array>
#include <algorighm>
#include <cstdio>
#include <vector>
using namespace std;
int m[1005][1005]; // 定义一个足够大的全局二维数组，用于动态规划
/* 参数说明:
- vector<int> w: 该向量用于存储每个物品的重量
- vector<int> v: 该向量用于存储每个物品的价值
- int c: 背包的容量
*/
int knapsack01(vector<int> w, vector<int> v, int c){
int n; // 由于每样物品只有一个
n = w.size(); // 所以题目中所需的n可以通过求任意一个向量的长度而获得
for(int i = 0; i < n; i++){ // 动态规划开始。i表示第i件物品
for(int j = 0; j <= w; j++){ // j表示思路1中背包重量的子集
if (i == 0 || j == 0){ // 第0个或背包重量为0时，直接赋值为0
m[i][j] = 0;
}
else if(w[i - 1] <= j){ // 第i个物品如果可以放到背包中的话
m[i][j] = max(m[i-1][j], (m[i-1][j-w[i - 1]] + v[i - 1]));
} // 最大值在放与不放中挑选
else{ // 如果物品过重，不放
m[i][j] = m[i - 1][j];
}
}
}
return m[n][c];
}
#!/usr/bin/env python3
# encoding: utf-8
def knapsack01(w, v, c):
"""
:param w: 每种物品重量的数组
:param v: 每种物品价值的数组
:param c: 背包的重量
:return: 答案
"""
n = len(w) # n可以直接通过求任一数组长度求得
m = [[0 for i in range(c + 2)] for j in range (n + 2)] # 构造一个二维数组用于存储动态规划的结果
for i in range(n + 1): # 动态规划开始，i代表第i个物品
for j in range(c + 1): # j 代表思路1中的重量子集
if (i == 0) or (j == 0): #第0个直接给0
m[i][j] = 0
elif (w[i - 1] <= j): # 如果能放进去
m[i][j] = max(m[i-1][j], (m[i - 1][j - w[i - 1]]) + v[i - 1]) #结果从放与不放中挑选
else: #如果放不进去
m[i][j] = m[i - 1][j] #就不要放
return m[n][c] #返回我们要求的答案
分数背包
预设条件与01背包相同。与01背包的不同点在于，它可以将物品拆开放。比如，放一半的物品A，2/3的物品B。
在分数背包问题中，我们要打破01背包时“放”与“不放”二分选择的思维惯性，而应这样思考：
暴力解法是将所有可能性比较一遍，然后取最大。但是这样做的复杂度极高，至少是指数级O(n 2 )。
那么是否有更优解？答案是有的。
大家购物时都会考虑性价比，是不是？那么，分数背包问题也可以从这个考虑。我们可以把所有东西的性价比算出来，然后将物品依性价比排序，由高到低，一个一个地放。如果物品放不进去过重放不进去，那么可以放一部分进去，直到放满为止。
那么，复杂度便降到了O(n*logn).
简单吗？对！用贪心算法就可以了！
代码实现如下：
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
class Items:
def __init__(self, w, v):
self.weight = w
self.value = v
self.ppr = w / v # 'ppr' means Price-Performance Ratio
def getAnswer(items, wk):
'''
:param items: a list which contains some Items
:param wk: the weight of a knapsack
return: the biggest value
'''
items.sort(key = lambda a: a.ppr, reverse = True)
n = len(items) # We can gain "n" through the length of the list "items".
bv = 0.0 # Define the biggest value.
cw = 0 # Define the "current weight".
for i in range(n):
if ((cw + items[i].weight) <= wk):
bv += items[i].value
else:
bv += items[i].value * ((k - cw) / items[i].weight)
return bv
if __name__ == '__main__':
a = int(input("需要几个背包？"))
for i in range(a):
items = list() # items用于表示物品
k = eval(input("第{}个背包的重量是：".format(i + 1)))
n = int(input("请输入物品个数："))
print("先输重量，再输价值")
for j in range(n):
w, v = map(int, input().split()) # w：重量，v价值
an_item = Items(w, v)
items.append(an_item)
# J循环结束后就可以开始获取答案了
val = getAnswer(items, k)
print(val, "\n")
References
- Hetland M L. Python Algorithms: mastering basic algorithms in the Python Language[M]. Apress, 2014.
- 背包问题九讲
- 动态规划（geeksforgeeks）
- 01背包问题吐血详解
- 背包问题详解：01背包、完全背包、多重背包
- 0-1 Knapsack Problem | DP-10
- Fractional Knapsack Problem
- 01背包和部分背包问题分析
