考虑下面的整数线性规划问题:【图片】其中:【图片】【图片】是非负整数,且【图片】下面( )是正确求解过程
A.
首先给出该问题的子问题描述: 且 的最优值为m(j) ,也就是m(j)表示在背包容量是j的时候背包问题的最优值。 由背包问题的最优子结构性质,可以建立计算m(j)的递归关系式如下:
B.
首先给出该问题的子问题描述: 且 的最优值为m(i,j) ,也就是m(i,j)表示在背包容量是j,可以选择物品1,2,...,i的时候背包问题的最优值。 由背包问题的最优子结构性质,可以建立计算m(i,j)的递归关系式如下: 其中初始值,m(0,j)=m(i,0)=0, m(i,j)=
C.
首先给出该问题的子问题描述: 且 的最优值为m(i,j) ,也就是m(i,j)表示在背包容量是j,可以选择物品1,2,...,i的时候背包问题的最优值。 由背包问题的最优子结构性质,可以建立计算m(i,j)的递归关系式如下: m(i,j)= 其中初始值,m(0,j)=m(i,0)=0, m(i,j)=
D.
可以用贪心算法求解。按照ai递增排序,依次选择第i个物体,只要选择的物体的总值小于b即可