背包问题
总共n个物件，每个物件的重量为
，是个Integer,每个物件价值为
，背包能装下的重量为S，求每次获取最大价值的装法。比如
总共有3个物件，背包限量为5kg。物件分别为
A价值10元，4kg
B价值4元，2kg
C价值7元，3kg
复制代码分析
要往背包里面去装东西，那么如果我去装某个物件，那么我将获取多少的价值，同时，损失的重量是多少？
从图的角度来看
每个边可以看做是添加一个物件，它的权值可以看做是获取的价值，要获取最大的价值，即是求权值是负权重的边的最短路径。
每个节点包含两个信息，当前要添加的物件，以及当前背包的重量。
要获取的最短路径为从S出发，到done为止。
- A->B->C->done表示选择物件的顺序，以及到最后结束;
- 0-5表示背包当前的重量；S表示开始的地方；
- 其中的A,0表示我要从A开始选择添加还是不添加，添加之前包的重量为0
- 如果选择直接从S到A,1表示背包最多只装4kg,存在浪费
从A开始挑选，有两种选择，使用A和不使用A，如果挑选A，那么背包将增重为4kg,如果不挑选A，背包没有增重,然后去挑选B
耗时：图中节点数为O(nS)，每个节点最多两条边，边数为O(nS),使用DAG的耗时为O(V+E)=O(nS)
从动态规划来看
背包里头可以选择不装，装A，再装B等，每添加一个物件，就会获取一些价值，占据一定的重量，因此需要考虑背包能装的重量以及背包已经有的价值是多大。装与不装需要获取一个最优解：
背包里头刚开始什么都没有，也就是刚开始的时候什么都不拿，背包中的价值都是0。
| A | B | C | 什么都不拿 | |
|---|---|---|---|---|
| 0 | 0 | |||
| 1 | 0 | |||
| 2 | 0 | |||
| 3 | 0 | |||
| 4 | 0 | |||
| 5 | 0 |
横轴表示要装的物件，纵轴表示背包的重量，每个单元格表示对应重量中背包中的价值
然后考虑C，根据最优解的计算方式，比较
已知 DP(什么都不拿,背包重量)的价值肯定是0，而C的重量为3kg所以只有当背包重为3的时候才取得价值，但是不能再拿C了，会超重
| A | B | C | 什么都不拿 | |
|---|---|---|---|---|
| 0 | 0 | 0 | ||
| 1 | 0 | 0 | ||
| 2 | 0 | 0 | ||
| 3 | 7 | 0 | ||
| 4 | 7 | 0 | ||
| 5 | 7 | 0 |
考虑开始拿B，B获取的时候就是2kg：
当重量小于2是，都是0，等于2时，可增加B，产生价值
| A | B | C | 什么都不拿 | |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 0 | |
| 2 | 4 | 0 | 0 | |
| 3 | 7 | 0 | ||
| 4 | 7 | 0 | ||
| 5 | 7 | 0 |
继续看能否加重，比较的是背包重量为3
DP(拿C,3)=7>，DP(拿C+B，2)+B的价值 =4
再拿B就只是增加了B的重量和价值，因为DP(c,2)=0，背包中仅仅只有B占2kg
| A | B | C | 什么都不拿 | |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 0 | |
| 2 | 4 | 0 | 0 | |
| 3 | 7 | 7 | 0 | |
| 4 | 7 | 7 | 0 | |
| 5 | 7 | 0 |
继续看B的加重，比较背包重量为4,没有1kg的物品，无法添加，然后背包总量为5，可以拿一个B一个C
DP(拿C,5)=7 < DP(拿C+B，4)+B的价值 = 7+4
此时容量为5，而DP(C,4)实际只占据了3kg，有2kg富余，可以继续添加1个B
| A | B | C | 什么都不拿 | |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 0 | |
| 2 | 4 | 0 | 0 | |
| 3 | 7 | 7 | 0 | |
| 4 | 7 | 7 | 0 | |
| 5 | 11 | 7 | 0 |
同理考虑添加A
| A | B | C | 什么都不拿 | |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 4 | 4 | 0 | 0 |
| 3 | 7 | 7 | 7 | 0 |
| 4 | 10 | 7 | 7 | 0 |
| 5 | 11 | 11 | 7 | 0 |
添加物品需要考虑的是 不能超重，然后比较增加的价值和不加物件的价值，那个更优
总共的子问题个数是O(ns),单个子问题只是看那个获得的价值更大，只是常量的执行时间，也就是说总共的时间是O(ns)
伪多项式运行时间
从上面看到背包问题需要的时间为O(ns),其中s表示背包的最大容量，一个物件的最大允许放的大小就是S，存放在电脑上起码需要 logS 的空间。而总共的个数有 n 个需要处理，所以花销的空间大小为 O(nlogS),假设logS=b,即输入大小为 O(nb),那么运行时间为
,也就是随着输入的变大，运行时间会变成指数增长，但是如果b很小，就是多项式运行时间，这种称为伪多项式运行时间。
