-
算法视频讲解
1.七月算法:
http://v.youku.com/v_show/id_XMTQwMDMxMDA5Ng==.html?spm=a2h0k.8191407.0.0&from=s1.8-1-1.2
2.推荐:
http://v.youku.com/v_show/id_XMTQ3MzI0NzI2OA==.html?spm=a2h0k.8191407.0.0&from=s1.8-1-1.2&f=28521433
-
Online 0/1 Knapsack problem solver
http://www.karaffeltut.com/NEWKaraffeltutCom/Knapsack/knapsack.html
题目要求
有N件物品和一个容积为M的背包.第i件物品的体积w[i],价值是d[i].求解将哪些物品装入背包可使价值总和最大.每种物品只有一件,可以选择放或者不放(N<=3500,M>=13000)
解决方法
用F[i][j]表示取前i中物品,使他们总体积不超过j的最优取法取得的价值总和.要求F[N][M]
边界:
if(w[1] <= j) //拿第一种物品
F[1][j] = d[1];
else //第一种物品体积大于容积
F[1][j] = 0;
用F[i][j]表示取前i中物品,使他们总体积不超过j的最优取法取得的价值总和
递推:
F[i][j] = max(F[i-1][j],F[i-1][j-w[i]]+d[i])
F[i][j] = max(F[i-1][j] , F[i-1][j-w[i]]+d[i])
如果不取第i种物品,就是在前i-1种取若干,使总体积不超过j,F[i-1][j]
如果取第i件物品,容积就变成了j-w[i],j-w[i] >= 0,再加上第i种物品的价值
