LeetCode|LeetCode---背包问题
LeetCode上没有背包基本模型题，有几个简单的背包类的题，这里总结一下 。
目录
416. 分割等和子集
322. 零钱兑换
518. 零钱兑换 II
416. 分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
【LeetCode|LeetCode---背包问题】注意:
每个数组中的元素不会超过 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& nums) {int sum = accumulate(nums.begin(),nums.end(),0);
if(sum&1) return false;
sum = (sum>>1);
vectordp(sum+11,false);
dp[0] = 1;
int n = nums.size();
for(int i = 0;
i=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& 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& coins) {
int n = coins.size();
vectordp(amount+11,0);
dp[0] = 1;
for(int i = 0;
i 推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- LeetCode（03）Longest|LeetCode（03）Longest Substring Without Repeating Characters
- Leetcode|Leetcode No.198打家劫舍
- [leetcode数组系列]1两数之和
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- LeetCode|LeetCode 876. 链表的中间结点