问题描述
有$n$件物品，每件物品的重量为$w_i$，价值为$c_i$。现在需要选出若干件物品放入一个容量为$V$的背包中（每件物品至多选一次），使得在选入背包的物品重量之和不超过容量$V$的前提下，让背包中物品的价值之和最大，求最大价值。
解题思路
深度优先搜索
一种暴力解法，每一件物品按照“选”“不选”进行分支，可以构建出一棵树；对这棵树进行搜索，求出所有情况的物品价值之和，取最大值。
这种做法时间复杂度很高。一种可能的优化方法是，先将物品按照重量进行非递减排序，然后依次考虑每一个物品的选取与否。如果选取了当前物品，而导致超出背包容量，那么当前分支可以被剪去（直接返回结果即可）——这样达到剪枝效果。
动态规划
0-1背包问题是一种非常经典的可以用动态规划求解的问题。对于给定的$n$个物品、总容量为$V$的背包情况下，我们定义一个数组$\mathrm{dp[n][V]}$，其中
其中，$i\in \{0,1,\cdots,n-1\}, w\in \{0,1,\cdots,V\}$。
接下来考虑状态转移，也就是考虑第$i$个物品的选取问题：
- 若不选第$i$个物品，那么显然有
- 若选第$i$个物品，就得确保考虑前$i-1$个物品的子问题时，还有足够的容量支持$w_i$放入，即
综上，我们得到状态转移方程为
变体
分割等和子集
传送门：https://leetcode.cn/problems/partition-equal-subset-sum/description/
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。这个题其实可以这样理解：从一堆数字中选取若干个数字，使其和为指定的数（不妨记作target），那么我们可以将其转化为0-1背包问题，只不过这个问题中，每一个物品的重量和价值均相等。那么我们按照上述思路得到$\mathrm{dp}$数组后，只需判断$\mathrm{dp[n][V]}==V$是否成立即可。状态转移方程为
