LeetCode上没有背包基本模型题，有几个简单的背包类的题，这里总结一下 。
目录
416. 分割等和子集
322. 零钱兑换
518. 零钱兑换 II
416. 分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
基本的0-1背包问题
class Solution {
public:bool canPartition(vector<int>& nums) {int sum = accumulate(nums.begin(),nums.end(),0);if(sum&1) return false;sum = (sum>>1);vector<bool>dp(sum+11,false);dp[0] = 1;int n = nums.size();for(int i = 0;i<n;++i)for(int j = sum;j>=nums[i];--j)dp[j] = dp[j] || dp[ j - nums[i] ];return dp[sum];}
};
322. 零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1
完全背包问题
class Solution {
public:int f[111111];int coinChange(vector<int>& coins, int amount) {memset(f,0x3f,sizeof f);f[0] = 0;int n = coins.size();for(int i = 1;i<=n;++i)for(int j = coins[i-1];j<=amount;++j){f[j] = min(f[j],f[j-coins[i-1]]+1);}return f[amount] == 0x3f3f3f3f? -1:f[amount];//f[j]如果是0就返回false,反之ture}
};
518. 零钱兑换 II
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 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
基本完全背包问题
class Solution {
public:int change(int amount, vector<int>& coins) {int n = coins.size();vector<int>dp(amount+11,0);dp[0] = 1;for(int i = 0;i<n;++i){for(int j = coins[i];j<=amount;++j)dp[j] += dp[j-coins[i]];}return dp[amount];}
};