福永网站的建设,开发一款app软件需要多少钱,怎样做好营销推广,深圳网站建设哪家公司便宜对前面几道题目做一下总结。
问题枚举多阶段限制条件目标值0-1背包每种物品#xff1a;放/不放每种物品一个阶段不能超过总重量w放完索引物品后#xff0c;总重量最大双11每种物品#xff1a;买/不买每种物品一个阶段w总价格3w放完索引物品后#xff0c;总价格是大…对前面几道题目做一下总结。
问题枚举多阶段限制条件目标值0-1背包每种物品放/不放每种物品一个阶段不能超过总重量w放完索引物品后总重量最大双11每种物品买/不买每种物品一个阶段w总价格3w放完索引物品后总价格是大于w的最小值矩阵最短路径长度每个位置移动的方向向下/右每个位置一个阶段到达(n-1,n-1)最短路径长度最长递增子序列每个元素是否在递增子序列中加/不加以第0个元素结尾以第1个元素结尾…以第n-1个元素结尾考察完数组所有元素选择长度最长的莱文斯坦编辑距离当前比较的两个字符不相同时候的处理方式添加/删除/替换字符的位置:0,1,2…考察完数组所有字符选择编辑距离最短的硬币找零符合条件不同币值的硬币第0种、第1种…支付1元、2元…w元支付w元最少硬币数量
问题状态转移表维度状态转移表值状态转移方程答案0-1背包(i,cw)i:第i个物品cw:当前总重量true/false:能否达到那个重量state[n-1][j]true,j最大双11(i,presum)i:第i个物品cw:当前总价格true/false:能否达到那个价格state[n-1][j]true,jw且最小矩阵最短路径长度(i,j)i:第i行j:第j列到达(i,j)的最短路径长度min_dist(i,j)matrix[i][j]min(min_dist(i-1,j-1),min_dist(i-1,j))min_dist(n-1,n-1)最长递增子序列(i)i:以第i个元素结尾以第i个元素结尾的最长递增子序列长度max_lis(i)max(max_lis(j))1 j0,1,2…i-1,a[i]a[j]max_lis(i)的最大值,i0,1,2…n-1莱文斯坦编辑距离(i,j) i:比较字符a[i]j:比较字符b[j]最少编辑次数a[i]b[j],min_editmin(min_edist(i-1,j-1),min_edist(i-1,j)1,min_edist(i,j-1)1)a[i]!b[j],min_editmin(min_edist(i-1,j-1),min_edist(i-1,j),min_edist(i,j-1)1)1min_edist(m-1,n-1)m:a字符串的长度n:b字符串的长度硬币找零(x) x:已选择硬币总和最少硬币个数F(i)min(F(x-cic_ici))1i0,1,2,…n-1,x-cic_ici0F(w)
根据表格回答以下问题。
1 目标状态与目标值是什么 根据题目回答。 考察完所有物品放入物品重量最大。 到达位置(n-1,n-1)最短路径长度。 考察完最后一个元素最长递增子序列长度。 支付w元最少应比数量。 两个字符串按位置字符比较完成最少编辑次数。 2 多阶段决策问题按照什么分阶段 按照目标状态分阶段。 考察完所有物品最大重量。那就按照物品分阶段。 到达(n-1,n-1)时的最短路径长度那就按照所在位置分阶段。 考察完数组最后一个元素后的最长递增子序列长度那就按数组中每一个元素分阶段。 考察完所有物品后总价格最低那就按照物品分阶段。 支付元时的最少硬币数量那就按照支付w-1、w-2…分阶段。 考察完两个字符串所有字符之后的最小编辑次数那就按照字符位置分阶段。
3 状态表的维度和值是什么 状态表的维度一般就是分阶段的维度。 按照物品分阶段状态表维度是物品所在下标。 按照矩阵位置分阶段状态表维度就是矩阵位置的横纵坐标。 按照支付多少元分阶段状态表维度就是支付总额。 按照字符位置分阶段状态表维度就是字符所在位置的下标。 特例0-1背包问题因为重量是限制条件状态表维度是物品下标和重量。 状态表的值一般就是目标值。 目标值是最少编辑次数状态表的值就是最少编辑次数。 目标值是硬币最少数量状态表的值就是硬币最少数量。 特例0-1背包问题因为重量是限制条件状态表的值true/false表示能不能达到某个重量。
4 状态转移方程是按照什么列出的 状态转移方程是按照业务条件列出的。 按照前进方向 按照硬币币值 按照字符相同不同时候的处理方式
