初学DP(3.5) – 完全背包 – Luogu P1616 疯狂的采药
2018年2月09日 / 周五 / 0
条评论
完全背包
我们先来回顾一下 01 背包
针对于有一定空间，一定数量的物品，每个物品只能放一个，我们可以把他当为 01 背包，它的状态转移方程是:
f[j]=max( f [ j – a [ i ] ] + a [ i ] , f [ j ] )
那么什么是完全背包呢?
针对于有一定空间，一定数量的物品，每个物品能放无数个的背包，我们称其为完全背包，
我们曾经 ...
初学DP (1) – 01 背包 – 装箱问题 & NOIP 2005 普及 第三题 采药
2018年2月06日 / 周二 / 1
条评论
DP
动态规划
我们知道，贪心的方法是取全局最优解，而 DP 是指通过解决局部最优解，来找到整个问题的最优解，我们来用看看下面这个求最短路的例子:
/ 2 \
1 - 3 - 5
\ 4 /
我们求从 1 到 5 的的最短路，首先我们应该求出 1->2/3/4 的最短路，我们已经知道了 f(1) ( 1 的最短路)=1，将其移动到并算出 1-& ...