走错路认错人
幼苗
共回答了13个问题采纳率:92.3% 举报
因为问题存在明显无后效性和决策阶段性
所以应当使用动态规划求解
设函数f[i][j]表示前i件物品其中放入背包j件的最大价值,这样就可以实现转移了.
f[i][j]=max(f[i - 1][j - 1] + v[i], f[i - 1][j]);
两个决策表示取与不取第i件物品
初始状态为f[i][0]=0,f[0][i]=0
答案为f[n][m]
程序实现非常简单,LZ自己想想就知道了,呵呵
如果实在需要,LZ可以再问我要
1年前
4