网站域名空间租用合同,资讯门户类网站模板,昌大建设始建于哪个地区,做网站公司(信科网络)474 一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小#xff0c;该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素#xff0c;集合 x 是集合 y 的 子集 。
示例 1#xff1a; 输入#xff1a;s…474 一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素集合 x 是集合 y 的 子集 。
示例 1 输入strs [10, 0001, 111001, 1, 0], m 5, n 3 输出4 解释最多有 5 个 0 和 3 个 1 的最大子集是 {10,0001,1,0} 因此答案是 4 。 其他满足题意但较小的子集包括 {0001,1} 和 {10,1,0} 。{111001} 不满足题意因为它含 4 个 1 大于 n 的值 3 。
示例 2
输入strs [10, 0, 1], m 1, n 1输出2解释最大的子集是 {0, 1} 所以答案是 2 。
此时大家可以回想一下01背包的递推公式dp[j] max(dp[j], dp[j - weight[i]] value[i]);
对比一下就会发现字符串的zeroNum和oneNum相当于物品的重量weight[i]字符串本身的个数相当于物品的价值value[i]。
这就是一个典型的01背包 只不过物品的重量有了两个维度而已。
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m 1, vectorint (n 1, 0)); // 默认初始化0for (string str : strs) { // 遍历物品int oneNum 0, zeroNum 0;for (char c : str) {if (c 0) zeroNum;else oneNum;}for (int i m; i zeroNum; i--) { // 遍历背包容量且从后向前遍历for (int j n; j oneNum; j--) {dp[i][j] max(dp[i][j], dp[i - zeroNum][j - oneNum] 1);}}}return dp[m][n];}
};总而言之本题只是把背包提升了一个维度总体说来还属于01背包
此时我们讲解了0-1背包的多种应用
纯 0 - 1 背包 (opens new window)是求 给定背包容量 装满背包 的最大价值是多少。416. 分割等和子集 (opens new window)是求 给定背包容量能不能装满这个背包。1049. 最后一块石头的重量 II (opens new window)是求 给定背包容量尽可能装最多能装多少494. 目标和 (opens new window)是求 给定背包容量装满背包有多少种方法。本题是求 给定背包容量装满背包最多有多少个物品。
所以在代码随想录中所列举的题目都是 0-1背包不同维度上的应用大家可以细心体会
完全背包理论基础
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品都有无限个也就是可以放入背包多次求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是每种物品有无限件。
// 先遍历物品在遍历背包
void test_CompletePack() {vectorint weight {1, 3, 4};vectorint value {15, 20, 30};int bagWeight 4;vectorint dp(bagWeight 1, 0);for(int i 0; i weight.size(); i) { // 遍历物品for(int j weight[i]; j bagWeight; j) { // 遍历背包容量dp[j] max(dp[j], dp[j - weight[i]] value[i]);}}cout dp[bagWeight] endl;
}
int main() {test_CompletePack();
}
// 先遍历背包再遍历物品
void test_CompletePack() {vectorint weight {1, 3, 4};vectorint value {15, 20, 30};int bagWeight 4;vectorint dp(bagWeight 1, 0);for(int j 0; j bagWeight; j) { // 遍历背包容量for(int i 0; i weight.size(); i) { // 遍历物品if (j - weight[i] 0) dp[j] max(dp[j], dp[j - weight[i]] value[i]);}}cout dp[bagWeight] endl;
}
int main() {test_CompletePack();
}总结完全背包与01背包的区别就是遍历背包时从前往后遍历并且遍历物品和遍历背包的顺序可以颠倒
518 零钱兑换II
给你一个整数数组 coins 表示不同面额的硬币另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
本题是给定背包大小求有多少种方法能放满递推公式和之前一样
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
class Solution {
public:int change(int amount, vectorint coins) {vectorint dp(amount 1, 0);dp[0] 1;for (int i 0; i coins.size(); i) { // 遍历物品for (int j coins[i]; j amount; j) { // 遍历背包dp[j] dp[j - coins[i]];}}return dp[amount];}
};
