【文件属性】：
文件名称：leetcode股票最大收益java-Algorithm:Algorithm算法设计与分析
文件大小：680KB
文件格式：ZIP
更新时间：2021-06-30 09:11:06
系统开源
leetcode股票最大收益java
Algorithm
Algorithm
算法设计与分析
一、动态规划
1.单调队列优化多重背包
原始状态转换方程：
$$
c[i]
=
min(s[i],
\quad
j/v[i])
$$
$$
f[i][j]
=
max(f[i-1][j-kv[i]]+kw[i])
,0<=k<=c[i]
$$
v[i]：每件第i类物品的耗费
s[i]：第i类物品总数
w[i]：每件第i类物品的收益
优化：
$$
a
=
j/v[i],\quad
b=j
%
v[i]
$$
$$
j
=
a
*
v[i]
+
b
$$
$$
f[i][j]
=
max(f[i-1][(a-k)v[i]+b]+kw[i])
$$
$$
k'
=
a
-
k
$$
$$
f[i][j]
=
max(f[i-1][k'*v[i]+b]-k'w[i]+aw[i])，
a-c[i]
<=
k
<=
a
$$
k'：第i类物品还有多少件未装进背包
可以发现：
$$
f[i-1][k'*v[i]+b]
-
k'w[i]+aw[i]
$$
只与
k'
有关，而这个
k
'是一段连续的。我们要做