anla858
幼苗
共回答了23个问题采纳率:82.6% 举报
37=9+12+5+11(2,4,6,8)20=3+7+3+7
i:2, v:3,c[2]=3,w[2]=9, f[0]=0, old f[3]=4, new f[3]=9
i:4, v:10,c[4]=7,w[4]=12, f[3]=9, old f[10]=19, new f[10]=21
i:6, v:13,c[6]=3,w[6]=5, f[10]=21, old f[13]=25, new f[13]=26
i:8, v:20,c[8]=7,w[8]=11, f[13]=26, old f[20]=36, new f[20]=37
1年前
追问
4
举报
anla858
首先用ci、wi代表第 i 种物品的重量、价值,然后我们将在总重量不超过Y的前提下,前 j 种物品放入背包的最大总价值定义为A(j, Y)。 A(j, Y)的递推关系为: A(0, Y) = 0 A(j, 0) = 0 A(j, Y) = max { A(j - 1, Y), wj + A(j - 1, Y - cj) }, j=1,2,...,9 通过计算A(9, 20)即得到最终结果(dp)。 伪代码: for i=1 to 9 for v=20 to 0 f[v]=max{f[v],f[v-c[i]]+w[i]}; //由于A(j,Y)计算出后,A(j-1,Y)不再有用,这里左侧f[v]代表A(j,v),右侧f[v]代表A(j-1,v)