算法笔记-动态规划

27 February 2014

DP好难啊…T_T

智商不够只能慢慢看了…T_T


背包问题


先把背包九讲放在这里镇着.

01背包问题


有n个重量和价值分别为wi, vi的物品. 从这些物品中挑出总重量不超过W的物品. 问能挑出的最大价值为多少.


最容易想到的方法是对每一个物品是否放入背包试一下.


DP中貌似分析出状态转移方程是很重要的.(就像高中数学的递推表达式…

那么分析一下这个问题的状态转移. 假定有dp[i][j]表示从前i个物品中选出总重量不超过j的物品时的最大价值. 很显然dp[0][j] = 0. 对于任一i, j, 如果w[i] > j那么dp[i+1][j] = dp[i][j], 否则dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]] + v[i]). 公式如下:


参考代码:


感谢kid177 ! 把上面的代码降到了一维~



完全背包问题


有n种重量和价值分别为wi, vi的物品. 从中挑选总重量不超过W的物品, 求价值总和的最大值. 每种物品可以挑选任意多件.

还是用上面的dp[i][j]那么现在递推关系变成了这样:

然后注意一下在dp[i+1][j]中选择k(k>=1)个的情况与在dp[i+1][j-w[i]]中选择k+1个情况相同. 所以dp[i+1][j]中k>=1的部分已经在dp[i+1][j-w[i]]中计算过. 上面的式子可以这样变形:

参考代码:


多重部分和问题


有n种不同大小的数字ai, 每种各mi个. 判断是否可以从这些数字中选出若干使它们的和恰好为K.


用dp[i][j]表示前i种数相加得到j的时候第i种数最多能剩余多少个(不能得到j的时候为-1). 那么如果前i-1种数相加能得到j的话, 第i个数就可以留下mi个; 如果前i种数加和为j-ai时时第i种数还剩下k(k>0)个的话, 那么dp[i][j]就等于k-1. 这样可以得到下面的递推式:



最长上升子序列


序列和字符串不同不需要连续.

长为n的数列a0, a1, … , an-1. 求出这个序列中的最长上升子序列的长度. 最长上升子序列是指对于任意的i<j都有ai<aj. 限制条件1 <= n <= 1000, 0 <= ai <= 1000000.


dp[i]为长度为i的最长上升子序列的末尾元素的最小值(不存在即为INF).


标签:
  • Algorithm
comments powered by Disqus