1. 背包问题
先从栗子出发，你是一个有理想的吃货，你的肚子只能容纳5kg的东西，为了保证你的营养最大化，有以下几种食物可以选择
* 黄瓜 1kg 5营养（没错！营养就是单位）
* 西红柿 1kg 8营养
* 米饭 2kg 4营养
* 牛肉 3kg 10营养
动用吃货的小脑筋，就知道，营养最大化的选择是
牛肉+黄瓜+西红柿 共23点营养！
我的大脑是怎么计算的呢？
first blood：画出一个最优营养表格
| 食物 v\w |质量| 价值 |0kg |1kg | 2kg |3kg| 4kg |5kg |
| ------|------| ------ | ------ | ------ | ------ | ------ |------ |
|黄瓜 |1kg |5|0| 5 | 13 |13 | 17 |23 |
| 西红柿 |1kg |8|0| 8 | 8 |12 | 18 |18 |
| 米饭 |2kg|4| 0|0 | 4 |10 | 10 |14 |
| 牛肉 |3kg|10|0|0|0 |10| 10 |10 |
看不懂？容我解释
思路详解
d(i,w)代表肚子能吃w千克食物时，是否吃食物i的最大营养值(最优解)
假设1 放or不放牛肉
size（西红柿）=3kg，当背包大小小于3kg时，牛肉都放不进去，此前背包的总价值都为d=0（w=1kg，w=2kg），此后背包价值为d（牛肉，w）=10（w>=3）
假设2 放or不放米饭
size（米饭）=2kg，当背包价值小于2kg时，米饭是放不进去的，使d（米饭，w）=d（牛肉，w）；
，当w>=2kg时，就要开始判断，是放进米饭的价值大呢，还是不放米饭的价值大？
放米饭的价值为 d（米饭，w）=v[米饭]+d（牛肉，w-s[米饭]）
不放米饭的价值为 d（米饭，w）=d（牛肉，w）
w=2时，d（米饭，2）=max（v[米饭]）+d（牛肉，2-2），d（牛肉，2））=4
w=3时，d（米饭，3）=max（v[米饭]）+d（牛肉，3-2），d（牛肉，3））=10
同理 d（米饭，4）=d（米饭，5）=10
假设3 放or不放西红柿
size（西红柿）=1kg，当背包价值小于1kg时，西红柿是放不进去的，使d（西红柿，w）=d（米饭，w）；
放西红柿的价值为 d（西红柿，w）=v（西红柿）+d（米饭，w-s[西红柿]）
不放西红柿的价值为 d（西红柿，w）=d（米饭，w）
w=1时，d（西红柿，1）=max（v[西红柿]）+d（米饭，w-s[西红柿]）,d[米饭,1]）=8
w=2时，d（西红柿，2）=max（v[西红柿]）+d（米饭，w-s[西红柿]）,d[米饭,2]）=8
w=3时，v（西红柿）+d（米饭，w-s[西红柿]）=8+d（米饭，2）=12>d[米饭]=8,故d(西红柿，3)=12
同理，v（西红柿，4）=18，v（西红柿，5）=18.
假设4 放or不放黄瓜.
size（黄瓜）=1kg，当背包价值小于1kg时，黄瓜是放不进去的，使d（黄瓜，w）=d（西红柿，w）；
至于d的值，如图。
** 每一次的肚子选择，都是假设物品a放入了肚子，然后在放入与不放的假设中找到最优，即
全局最优解包含局部最优解，自顶向下寻找最优解，自底向上求最优解
**
咳咳，敲重点了哈，动态规划最重要的问题是什么？
** 是问题中的状态和状态转移方程是什么**。
诺。
d(i, j)=max{ d(i+1, j), d(i+1,j-V[i]) + W[i] }
即假设放入物体否吃进肚子里，一层一层考虑。就像下表中，先从3kg的牛肉放起。
| 食物 v\w |质量| 价值 |0kg |1kg | 2kg |3kg| 4kg |5kg |
| ------|------| ------ | ------ | ------ | ------ | ------ |------ |
|黄瓜 |1kg |5|0| 5 | 13 |13 | 17 |23 |
| 西红柿 |1kg |8|0| 8 | 8 |12 | 18 |18|
| 米饭 |2kg|4| 0|0 | 4 |10 | 10 |14 |
| 牛肉 |3kg|10|0|0|0 |10| 10 |10 |
先放牛肉的写法
for(int j = 0; j <= c; j++)
if(j < w[n]) m[n][j] = 0; //j小于w[n],所对应的值设为0，否则就为可以放置
else m[n][j] = v[n];
//对剩下的n-1个物品进行放置。
int i;
for(i = n-1; i >= 1; i--)
for(int j = 0; j <= c; j++)
if(j < w[i])
d[i][j] = d[i+1][j];//如果j < w[i]则，当前位置就不能放置，它等于上一个位置的值。
//否则，就比较到底是放置之后的值大，还是不放置的值大，选择其中较大者。
else d[i][j] = d[i+1][j] > d[i+1][j-w[i]] + v[i]?
d[i+1][j] : d[i+1][j-w[i]] + v[i];
}
先放黄瓜的写法
//本例中n=4，C=5
//返回最大值
function max(a, b) {
var result = a > b ? a : b;
return result;
}//其实js有内置的Math.max()
var value = [5, 8, 4, 10],
size = [1, 1, 2, 3],
d = [],
n = 4,
C = 5;
//初始化数组
for (var k = 0; k <= n; ++k) {
d[k] = [];
}
for (var i = 0; i <= n; ++i) {
for (var w = 0;w <= C; ++w) {
d[i][w] = (i == 0) ? 0 : d[i - 1][w];
if (i > 0 && j >= size[i - 1])
d[i][w] = max(d[i-1][w], d[i - 1][w - size[i - 1]] + value[i - 1]);
}
}
console.log(d[n][C], d[1][1])
//乾坤大循环后，得出d[n][c]
背包问题中，我最困惑的点是，你放了这个物品进去，怎么确保这次放的对以后的选项来说是最好的选择。
对于一件物品
2. 例题
链接：https://www.nowcoder.com/questionTerminal/9ba85699e2824bc29166c92561da77fa
来源：牛客网
一种双核CPU的两个核能够同时的处理任务，现在有n个已知数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb，每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理，现在需要设计一个方案让CPU处理完这批任务所需的时间最少，求这个最小的时间。
3. 资料
动态规划之背包问题（一）
动态规划之01背包问题--表格思路来源
通过金矿模型介绍动态规划
网友评论