小白的学习笔记——背包问题(1)(01背包，01背包优化，完全背包)_给定n个珠宝,第i个珠宝的重量是一个正整数w[i],价值是d[i],每个珠宝都是不可拆分

0：写在前面

  这里是一只纯小白(●ˇ∀ˇ●)，最近闲来无事研究了一下背包问题。小白想写几篇博客来加深一下理解。文章可能写的很烂，欢迎大佬们指正。如果这些文章也能帮到你，那就太好了(￣▽￣)"。

1：梦开始的地方——01背包

先上问题：
  夜黑风高之时，你——立志成为天下第一盗的素人盗贼，悄无声息的潜入了一家珠宝店。店里有n件珠宝，其中第i件物品的重量为w[i]，价值为v[i]，而你的背包最大承载量为p，你会如何选择，使自己偷走的珠宝价值最大…(因为对于每件物品，只可选择拿或者不拿，所以这类问题被形象的称为01背包问题)

先给出一组数据：n=3，p=9，w，v如下：

  你面对着这三件珠宝陷入了沉思…
  咋搞？
  首先，你想到了，偷，就要偷最贵的。100块和50块掉在地上，你捡哪张？只要不是思想出了问题，都会捡那张红色的吧(什么？全都要？贪心的人没有好果子吃哦)。于是，你直接抓起了第一件珠宝，看了一下，其他珠宝也装不进去了，那就跑路吧~
  这时，你没注意到，角落里传来了一道诡异的目光…
  一个小时后，你躺在床上，看着珠宝，心想”今天干了票大的，美滋滋，如果背包大一点，我将绝杀，可惜大不得“。突然，你意识到了一个问题，你没装进去的两件珠宝，加起来总重量是9，总价值15，远大于你现在手里的这件…（这就是贪心思想解决不了背包问题的原因———对于背包问题，贪心得到的局部最优解的组合不一定是整体最优解）
  你高呼自己是个铁憨憨，如果让你重新来过，你一定会仔细思考。这时，随着一道闪光，一位身穿长袍，仙风道骨的精神小伙出现在你面前。小伙剑眉星目，眉宇间透露着睿智的光辉,你盯着他的眼睛，仿佛看到了宇宙的深邃，但是比起那深邃，果然，最令你震惊的，还是男子帅气的面容，为什么，世上会有这么帅的人…
  ：“你是谁？”
  ：“谁也不是，只是一个流浪者。”我说到。：“我说，你励志成为天下第一盗？可你这今晚干的什么事啊？就这？”
  ：“害在这阴阳怪气呢？给爷爬爬爬！”
  ：“喂，憨憨，给你第二次机会的话，你还会装第一件珠宝吗？”
  ：“想也知道不可能啊喂，我有这么憨憨吗？啊所以你到底是——”
  ：“第七式：两极反转——”
  当你再次睁开眼睛时，你发现，自己竟然回到了一个小时之前。
  ：“我会助你成为天下第一大盗，所以，面对这三件珠宝，做出选择吧。”
  “虽然还没搞清这是什么状况，但是不是代表我可以重偷一次了？”你想到
  重新面对三件珠宝，你认真的想了下：
    1：对于每件物品，你只有两种选择——拿它，或者是不拿。
    2：拿这件物品，意味着我现在剩余空间可以装下，至于拿不拿，要看它值不值。
  把整个大问题拆开，你提出了子问题，“拿第一件，前两件，前三件物品时，我得到的最大价值是多少呢？”
  “机智！”我赞赏到。
  “这个问题，该怎么接解决呢？”
  为师帮你一手——
  设一个二维数组f[i][j],其中i表示前i件物品（一定要注意是前i件），j表示当前剩余的容量，f[i][j]就表示在剩余容量为j时，选取前i件物品的最大价值，于是不难得出下面的公式：
（这个公式要记住，它是所有背包问题的根源！！！）

其中，第一行表示第i件物品装不下的情况，此时最大价值还是和前i-1件物品的最大价值相同，而背包剩余的容量也还是j。第二行表示第i件物品可以装下的情况，它又分成两种情况：①不拿这件物品，此时获得的价值和前i-1件的最大价值是一样的；②拿这件物品，此时获得价值即是前i-1件物品，剩余空间为j-w[i]时的最大价值加上现在的第i件物品的价值。所以第i件物品可以装下时，最大的价值就是上述两种状况中最大的那个。
（②具体来说就是：前i-1件物品，剩余容量是j时，把第i件物品放进去，空间变为j-w[i]，而价值就是前i-1件物品，j-w[i]空间对应的价值再加上第i件物品的价值）

  有了这个神奇的公式，你就可以列出下面的表格：(为了方便，设i=0或j=0时f=0)
  （强烈建议自己动手写一下哦）

  这个表格告诉了我们最大能获得的价值，即是f[3][9]=15，基于上面的公式，我们就可以写出解决01背包问题的代码：（只给出关键部分，其余的偷个懒，省了==）

 for(int i=1;i<=n;i++)
 {
 	for(int j=1;j<=p;j++)
    {
    	if(j<w[i])
      		 f[i][j]=f[i-1][j];
        else
           	 f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
    }
  }
1
2
3
4
5
6
7
8
9
10

  写出这个程序后，你就可以得到你可以获得的最大价值了。
  不过，这个程序不会告诉你获得最大价值时是取了哪些物品。
  你愤怒的大喊：“声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】