马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。
您需要 登录 才可以下载或查看,没有账号?立即注册
×
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
- int max(int a,int b){
- return a>b?a:b;
- }
- int findMaxForm(char** strs, int strsSize, int m, int n) {
- int dp[m+1][n+1]={};
- //最多有i个0 j个1的最大子集大小
- int cnt0,cnt1=0,i,j,k;
- for(i=0;i<strsSize;i++){
- char *s=strs[i];
- int len=strlen(s);
- cnt0=0,cnt1=0;
- for(j=0;j<len;j++){
- if(s[j]=='0')cnt0++;
- else cnt1++;
- }
- for(j=m;j>=cnt0;j--){//先遍历物品,再遍历背包容量
- for(k=n;k>=cnt1;k--){//倒序遍历,避免被覆盖
- dp[j][k]=max(dp[j][k],dp[j-cnt0][k-cnt1]+1);
- }
- }
- }
- return dp[m][n];
- }
复制代码 完全背包
携带研究材料(第七期模拟笔试)
标题描述
小明是一位科学家,他需要参加一场紧张的国际科学大会,以展示本身的最新研究成果。他需要带一些研究材料,但是他的行李箱空间有限。这些研究材料包括实行设备、文献资料和实行样本等等,它们各自占据不同的重量,并且具有不同的代价。
小明的行李箱所能承担的总重量是有限的,问小明应该如何抉择,才能携带最大代价的研究材料,每种研究材料可以选择无数次,并且可以重复选择。
输入描述
第一行包含两个整数,n,v,分别表现研究材料的种类和行李所能承担的总重量
接下来包含 n 行,每行两个整数 wi 和 vi,代表第 i 种研究材料的重量和代价
输出描述
输出一个整数,表现最大代价。
输入示例
输出示例
提示信息
第一种材料选择五次,可以到达最大值。
二维数组会越界,接纳一维数组
完全背包与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背包相同
- #include<stdio.h>
- #define N 10005
- #define ll long long
- ll max(ll a,ll b){
- return a>b?a:b;
- }
- ll w[N]={},v[N]={};
- ll dp[N]={};
- int main(){
- int n,m,i,j;
- scanf("%d%d",&n,&m);
- for(i=0;i<n;i++){
- scanf("%lld%lld",&w[i],&v[i]);
- }
- //dp[i][j]表示[0,i]物品重量为j可重复选的最大价值
- for(j=w[0];j<=m;j++){
- if(j>=w[0])dp[j]=dp[j-w[0]]+v[0];
- }
- for(i=1;i<n;i++){
- for(j=m;j>=w[i];j--){
- dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
- }
- }
- printf("%lld",dp[m]);
- return 0;
- }
复制代码 518 零钱兑换
给你一个整数数组 coins 表现不同面额的硬币,另给一个整数 amount 表现总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。
假设每一种面额的硬币有无限个。
标题数据包管结果符合 32 位带符号整数。
示例 1:
- <strong>输入:</strong>amount = 5, coins = [1, 2, 5]
- <strong>输出:</strong>4
- <strong>解释:</strong>有四种方式可以凑成总金额:
- 5=5
- 5=2+2+1
- 5=2+1+1+1
- 5=1+1+1+1+1
复制代码 示例 2:
- <strong>输入:</strong>amount = 3, coins = [2]
- <strong>输出:</strong>0
- <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]
- int change(int amount, int* coins, int coinsSize) {
- int dp[amount + 1];
- //dp[j]表示凑满j钱的方法
- memset(dp, 0, sizeof (dp));
- dp[0] = 1;
- for(int i = 0; i < coinsSize; i++){
- for(int j = coins[i]; j <= amount; j++){
- if (dp[j] < INT_MAX - dp[j - coins[i]])dp[j] += dp[j - coins[i]];
- //防止相加数据超过int
- }
- }
- return dp[amount];
- }
复制代码
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。
|