动态规划-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种物品的价值

推荐阅读更多精彩内容

  • 背包问题(Knapsack problem) 是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品...
    NeoAndBob阅读 3,333评论 0 3
  • 一年级语文上册生字表 生字表一(共400字) 啊(ā)爱(ài)安(ān)岸(àn)爸(bà)八(bā)巴(bā)...
    meychang阅读 1,801评论 0 6
  • sì 支zhī茶chá 对duì 酒jiǔ,赋fù 对duì 诗shī,燕yàn子zi 对duì 莺yīng 儿é...
    每个人的孟母堂阅读 872评论 0 6
  • 树形动态规划,顾名思义就是树+DP,先分别回顾一下基本内容吧:动态规划:问题可以分解成若干相互联系的阶段,在每一个...
    Mr_chong阅读 1,195评论 0 1
  • 大家对于董卿当妈一事估计是知之甚少。而她也极少在公众面前提及自己的婚姻和小孩。 唯一的一次央视访谈还是在2012年...
    窗外阳光阅读 461评论 8 21
  • 文/木鱼书缃 周末听奶茶的歌,给十五岁的自己。 其实这首歌是我歌单里的老曲目,也不愿去追究奶茶唱这首歌时候的年龄,...
    木鱼书缃阅读 1,026评论 2 1
  • 午夜三点 我从梦中惊醒 习惯性的醒来发消息给你 意外的收到回复 想起你说的深度睡眠 到底是不是因为震动才醒来 我又...
    思兹念兹阅读 88评论 0 1
  • 在这个世界中,早在几亿年前就有了生命,而且被分为三界:天界,人界,魔界。而主宰着这个世界的是天界;可人界在之前的一...
    听风i说爱你阅读 200评论 0 1