用户登录

禁止注册!| 忘记密码?

分类:《动态规划》

解析动态规划问题(3)

解析动态规划问题(3)
用动态分析解决0-1背包问题 有n个物品,每个物品的重量为w[i],价值为v[i],购物车容量为W。选若干个物品放入购物车,在不超过容量的前提下使获得的价值最大。 问题分析 (1)分析最优解的结构特征 (2)建立具有...
162 views

解析动态规划问题(2)

解析动态规划问题(2)
最优三角剖分 与矩阵连乘的不同点 不同点就在于递归公式的不同,最优三角剖分的递归公式如下: 当i=j的时候,m[i][j]=0; 当i<j的时候,m[i][j]=min{m[i][k]+m[k+1][j]+w(v(i-1)vkvj)} 图解示例 我们以一个凸...
179 views