文件名称：leetcode股票最大收益java-Algorithm:Algorithm算法设计与分析
文件大小：680KB
文件格式：ZIP
更新时间：2024-07-20 02:57:46
系统开源
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 '是一段连续的。我们要做