leetcode day37 474

[复制链接]
发表于 2025-4-30 09:16:11 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?立即注册

×
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背包标题
1、确定dp数组寄义
dp[j] = max(dp[j], dp[j - weight] + value);
2、初始化为0
3、确定递推公式
因为物品的重量有了两个维度,以是用滚动数组解题,这里用二维数组。
留意:滚动数组双重for循环,必须先遍历物品,再遍历背包,同时背包要倒序遍历。
01背包递推公式dp[j] = max(dp[j], dp[j - weight] + value);
这里转化一下,01的个数相称于weight,value就是字符串本身的个数1
  1. int max(int a,int b){
  2.     return a>b?a:b;
  3. }
  4. int findMaxForm(char** strs, int strsSize, int m, int n) {
  5.     int dp[m+1][n+1]={};
  6.     //最多有i个0 j个1的最大子集大小
  7.     int cnt0,cnt1=0,i,j,k;
  8.     for(i=0;i<strsSize;i++){
  9.         char *s=strs[i];
  10.         int len=strlen(s);
  11.         cnt0=0,cnt1=0;
  12.         for(j=0;j<len;j++){
  13.             if(s[j]=='0')cnt0++;
  14.             else cnt1++;
  15.         }
  16.         for(j=m;j>=cnt0;j--){//先遍历物品,再遍历背包容量
  17.              for(k=n;k>=cnt1;k--){//倒序遍历,避免被覆盖
  18.                 dp[j][k]=max(dp[j][k],dp[j-cnt0][k-cnt1]+1);
  19.              }
  20.         }
  21.     }
  22.     return dp[m][n];
  23. }
复制代码
完全背包

携带研究材料(第七期模拟笔试)

标题描述

小明是一位科学家,他需要参加一场紧张的国际科学大会,以展示本身的最新研究成果。他需要带一些研究材料,但是他的行李箱空间有限。这些研究材料包括实行设备、文献资料和实行样本等等,它们各自占据不同的重量,并且具有不同的代价。
小明的行李箱所能承担的总重量是有限的,问小明应该如何抉择,才能携带最大代价的研究材料,每种研究材料可以选择无数次,并且可以重复选择。
输入描述

第一行包含两个整数,n,v,分别表现研究材料的种类和行李所能承担的总重量 
接下来包含 n 行,每行两个整数 wi 和 vi,代表第 i 种研究材料的重量和代价
输出描述

输出一个整数,表现最大代价。
输入示例

  1. 4 5
  2. 1 2
  3. 2 4
  4. 3 4
  5. 4 5
复制代码
输出示例

  1. 10
复制代码
提示信息

第一种材料选择五次,可以到达最大值。
二维数组会越界,接纳一维数组
完全背包与01背包不同点:物品可以重复取多次
1、二维数组情况
(1)dp[j]表现[0,i]物品重量为j可重复选的最大代价
 (2)初始化
    dp[0][j]=dp[0][j-w[0]]+v[0]
(3)递推公式
   dp[j]=dp[i-1][j];//不放物品i
   dp[j]=max(dp[i-1][j],dp[j-w]+v);
  这里是dp[j-w]+v,与01背包不同,dp[i-1][j-w]+v
2、一维数组
(1)dp[j]表现物品重量为j可重复选的最大代价
 (2)初始化
    dp[j]=dp[j-w[0]]+v[0]
与01背包不同,01背包初始化为01即可
(3)递推公式
dp[j]=max(dp[j],dp[j-w+v)
这里与01背包相同
  1. #include<stdio.h>
  2. #define N 10005
  3. #define ll long long
  4. ll max(ll a,ll b){
  5.     return a>b?a:b;
  6. }
  7. ll w[N]={},v[N]={};
  8. ll dp[N]={};
  9. int main(){
  10.     int n,m,i,j;
  11.     scanf("%d%d",&n,&m);
  12.     for(i=0;i<n;i++){
  13.         scanf("%lld%lld",&w[i],&v[i]);
  14.     }
  15.     //dp[i][j]表示[0,i]物品重量为j可重复选的最大价值
  16.     for(j=w[0];j<=m;j++){
  17.         if(j>=w[0])dp[j]=dp[j-w[0]]+v[0];
  18.     }
  19.     for(i=1;i<n;i++){
  20.         for(j=m;j>=w[i];j--){
  21.            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
  22.         }
  23.     }
  24.     printf("%lld",dp[m]);
  25.     return 0;
  26. }
复制代码
518 零钱兑换

给你一个整数数组 coins 表现不同面额的硬币,另给一个整数 amount 表现总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。
假设每一种面额的硬币有无限个。 
标题数据包管结果符合 32 位带符号整数。

  示例 1:
  1. <strong>输入:</strong>amount = 5, coins = [1, 2, 5]
  2. <strong>输出:</strong>4
  3. <strong>解释:</strong>有四种方式可以凑成总金额:
  4. 5=5
  5. 5=2+2+1
  6. 5=2+1+1+1
  7. 5=1+1+1+1+1
复制代码
示例 2:
  1. <strong>输入:</strong>amount = 3, coins = [2]
  2. <strong>输出:</strong>0
  3. <strong>解释:</strong>只用面额 2 的硬币不能凑成总金额 3 。
复制代码
示例 3:
输入:amount = 10, coins = [10]
输出:1

因为标题数据包管结果符合 32 位带符号整数。以是要用INT_MAX防止数组越界
一维数组
1、dp[j]表现装满j钱的方法数
2、初始化dp[0]=1
3、确定动规方程
二维dp 递推公式: dp[j] = dp[i - 1][j] + dp[j - coins]
压缩成一维:dp[j] += dp[j - coins]
  1. int change(int amount, int* coins, int coinsSize) {
  2.     int dp[amount + 1];
  3.     //dp[j]表示凑满j钱的方法
  4.     memset(dp, 0, sizeof (dp));
  5.     dp[0] = 1;
  6.     for(int i = 0; i < coinsSize; i++){
  7.         for(int j = coins[i]; j <= amount; j++){
  8.             if (dp[j] < INT_MAX - dp[j - coins[i]])dp[j] += dp[j - coins[i]];
  9.             //防止相加数据超过int
  10.         }
  11.     }
  12.     return dp[amount];
  13. }
复制代码


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。
继续阅读请点击广告
回复

使用道具 举报

© 2001-2025 Discuz! Team. Powered by Discuz! X3.5

GMT+8, 2025-7-9 10:23 , Processed in 0.224860 second(s), 33 queries 手机版|qidao123.com技术社区-IT企服评测▪应用市场 ( 浙ICP备20004199 )|网站地图

快速回复 返回顶部 返回列表