聊聊十五周算法训练营——背包问题

今天是十五周算法训练营的第十三周，主要讲背包问题专题。（欢迎加入十五周算法训练营，与小伙伴一起卷算法）,「背包问题：给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i]，价值为val[i]，现在让你用这个背包装物品，最多能装的价值是多少？」,状态有两个：背包的容量和可选择的物品,选择就是：装进背包或者不装进背包,刚才明确了状态，现在需要用dp数组把状态表达出来，刚才找到的「状态」，有两个，也就是说我们需要一个二维dp数组，一维表示可选择的物品，一维表示背包的容量。,dp[i][w]表示的就是对于[0……i]个物品，当前背包容量为w时的最大价值,dp[i][w]表示：对于前i个物品，当前背包的容量为w时，这种情况下可以装下的最大价值是dp[i][w]。,如果你没有把这第i个物品装入背包，那么很显然，最大价值dp[i][w]应该等于dp[i-1][w]。你不装嘛，那就继承之前的结果。,如果你把这第i个物品装入了背包，那么dp[i][w]应该等于dp[i-1][w-wt[i-1]] + val[i-1]。,首先，由于i是从 1 开始的，所以对val和wt的取值是i-1。,背包问题动态规划的结构,给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。,示例 1：,输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。,给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。,请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。,假设每一种面额的硬币有无限个。,题目数据保证结果符合 32 位带符号整数。,示例 1：,输入：amount = 5, coins = [1, 2, 5] 输出：4 解释：有四种方式可以凑成总金额： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1,有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。,每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：,如果 x == y，那么两块石头都会被完全粉碎； 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。,示例 1：,输入：stones = [2,7,4,1,8,1] 输出：1 解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]， 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。,给你一个整数数组 nums 和一个整数 target 。,向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：,例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。,示例 1：,输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 – 1 + 1 + 1 + 1 = 3 +1 + 1 – 1 + 1 + 1 = 3 +1 + 1 + 1 – 1 + 1 = 3 +1 + 1 + 1 + 1 – 1 = 3,