动态规划-01背包问题

• 算法视频讲解

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种物品的价值