六大算法之三:动态规划【转载】
等),填表的过程就是根据递推关系,从1行1列开始,以行或者列优先的顺序,依次填写表格,最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。 f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)} 算法实现的步骤 1、创建一个一维数组或者二维数组,保存每一个子问题的结果,具体创建一维数组还是二维数组看题目而定,基本上如果题目中给出的是一个一维数组进行操作,就可以只创建一个一维数组,如果题目中给出了两个一维数组进行操作或者两种不同类型的变量值,比如背包问题中的不同物体的体积与总体积,找零钱问题中的不同面值零钱与总钱数,这样就需要创建一个二维数组。 注:需要创建二维数组的解法,都可以创建一个一维数组运用滚动数组的方式来解决,即一位数组中的值不停的变化,后面会...阅读全文