首页 > 其他 > 详细

关于01背包问题

时间:2020-02-01 17:30:49      阅读:48      评论:0      收藏:0      [点我收藏+]
  关于伟大的DP,入门便是从背包问题开始,没错,背包分为01背包,完全背包,多重背包等。
  众所周知完全背包便是01背包的反向思想,那么什么是01背包?没错01背包,顾名思义0和1(废话),就是选(1)和不选(0)。
  有一大堆东西(n件),有价值(v),有重量(w),有一个承重(V)的背包,嗯没错,跟贪心差不多,求可以装到的西的价值之和最大。
  现在定义f数组,f[i]表示重量为i的背包(数组下标)能装到的最大价值,那么我们要求的答案就是f[V]。
  为何如此定义?
  因为动归的思想就是从子问题(小问题)下手,解决子问题再解决大一点的子问题,解决大一点的子问题,就解决更大的子问题从而解决整个问题。
  好比写文章,你得先学拼音,再习识字,再学习写字,再学习构思,再开始写文章。
  如何求f[i]呢?我们不妨枚举每一个物品。
  嗯,那么第一个for就出来了。
  for(int i=1;i<=n;i++)
  嗯,真香。
  然后呢枚举能装下这个物品的全部背包。
  for(int j=V;j>=v[i];j--)
  嗯,然后计算背包能装下的物品的最大价值之和。
  f[j]=max(f[j],f[j-w[i]]+v[i]);
  顾名思义前者,f[j]就是不选这个东西。
  后者f[j-w[i]]+v[i]便是选这个东西,+v[i]众所周知选这个物品就要加上他的价值。
  那么j-w[i]是何意义呢?
  嗯没错j指重量j,w[i]指这个物品的重量。
  在当前情况下我们不知道背包够不够装这个物品,所以我们必须要腾出w[i]的空间来装这个物品。
  那么f[j-w[i]]在这里表示的是,我腾出空间(丢掉一些东西)时可获得的最大价值。
  所以核心部分便是:
 for(int i=1;i<=n;i++)
    for(int j=V;j>=v[i];j--)
      f[j]=max(f[j],f[j-w[i]]+v[i]);
  然后呢
 printf("%d\n",f[V]);
  大功告成!

关于01背包问题

原文:https://www.cnblogs.com/BiuBiu-Miku/p/12249079.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!