Hi，大家好，我是编程小6，很荣幸遇见你，我把这些年在开发过程中遇到的问题或想法写出来，今天说一说
01背包问题详解_背包问题贪心算法,希望能够帮助你!!!。

问题描述

有一堆物品，具有各自的重量、价值，有一个一定容量的背包

装取物品，得到最大的价值。由于每个物品都有装或不装两个状态，即01状态，所以称为01背包问题。

暴力激活成功教程

最直接的思路是利用深度优先的思想，遍历所有的方案，每个物品有两种状态，共有2^n种可能方案。

动态规划

采用动态规划更加节约空间和时间。
假定物品为：苹果 重1 价值2
西瓜 重4 价值3
菠萝 重3 价值4
背包容量设定为5
为了计算方便，容量从0开始，物品情况也从0开始，初始化一个4x6的矩阵用来存放每个方案的价值，这样从第二行开始迭代，每次迭代的情况都一样，都可以用上一行的值来计算。
第二行只考虑只有苹果的情况，则
如果苹果重<=当前背包容量，则将苹果放入，如果还有空余重量则使用上一行的对应重量的价值，由于第一行都是0，所以+0，比较放入后的价值与上一行的价值，选择较大的价值填入。

第三行考虑增加西瓜的情况。
由于西瓜重4，所以容量为4时价值才开始与上一行不同，而容量为5时，放入西瓜后容量余1，所以使用上一行容量1对应的价值2与西瓜价值相加得5。

第四行考虑增加菠萝的情况。
由于菠萝重3，所以容量为3时价值才开始与上一行不同，容量为4时，放入菠萝后余1容量，与上一行对应值相加后为6，大于上一行容量4对应的值3，所以填入6，容量5同理填入6。

背包矩阵为

最大价值为矩阵最后一个元素6
由于只需要最大价值，而不需要过程，可以简化为一维形式。倒序更新每一列即可。

实例分析

1049. 最后一块石头的重量 II
      

class Solution { public: int sum = 0; int lastStoneWeightII(vector<int>& stones) { int sum = 0; int len = stones.size(); for(int i=0; i<len; i++){ sum += stones[i]; } int targetSum = int(sum/2); vector<int> array(targetSum+1); int with_re, without_re; for(int j=0; j<len; j++){ for(int i=targetSum; i>0; i--){ without_re = array[i]; with_re = (stones[j]<=i)?(stones[j]+array[i-stones[j]]):(array[i]); array[i] = max(without_re, with_re); } } return sum - 2*array[targetSum]; } }; 

今天的分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。