小明有N元钱去药店买口罩，药店里有6个品牌的口罩，A品牌2个装（2元），B品牌3个装（2元）、C品牌1个装（3元）、D品牌5个装（1元），E品牌4个装（5元），F品牌3个装（2元），由于限购每个品牌最多只能买一个，小明最多能买多少口罩？
[编程题]买口罩
- 热度指数：2211 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
import java.util.*;
public class Main{
public static void main(String[]args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int [] a = new int [] {0,2,3,1,5,4,3}; //个数
int [] b = new int [] {0,2,2,3,1,5,2};// 钱
int [][]dp = new int [7][n+1];
dp[0][0] = 0;
for(int i = 1; i <=6; i++){
for(int j = 1; j<=n;j++){
if(j<b[i]){
dp[i][j] = dp[i-1][j];//钱不够用了
}
else{
//不装第i个，和装了第I个比较
dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-b[i]]+a[i]);
}
}
}
System.out.println(dp[6][n]);
}
} 典型的01背包问题
发表于 2021-03-30 22:11:23
回复(0)
n=int(input())
res=0
dp=[[0 for i in range(n+1)] for j in range(7)]
mask=[(2,2),(3,2),(1,3),(5,1),(4,5),(3,2)]
for i in range(1,7):
for j in range(1,n+1):
if j>=mask[i-1][1]:
dp[i][j]=max(dp[i-1][j],mask[i-1][0]+dp[i-1][j-mask[i-1][1]])
else:
dp[i][j]=dp[i-1][j]
print(dp[-1][-1])
res=0
dp=[[0 for i in range(n+1)] for j in range(7)]
mask=[(2,2),(3,2),(1,3),(5,1),(4,5),(3,2)]
for i in range(1,7):
for j in range(1,n+1):
if j>=mask[i-1][1]:
dp[i][j]=max(dp[i-1][j],mask[i-1][0]+dp[i-1][j-mask[i-1][1]])
else:
dp[i][j]=dp[i-1][j]
print(dp[-1][-1])
发表于 2021-09-04 23:28:29
回复(0)
# 拿个纸计算 a =int(input()) if a >= 14: print(18) elif a == 0: print(0) elif a == 1: print(5) elif a == 2: print(7) elif a == 3: print(8) elif a == 4: print(8) elif a == 5: print(11) elif a == 6: print(11) elif a == 7: print(13) elif a == 8: print(13) elif a == 9: print(13) elif a == 10: print(15) elif a == 11: print(15) elif a == 12: print(17) elif a == 13: print(17)
发表于 2023-09-03 22:25:06
回复(0)
#include <stdio.h>
intmain() {
inta, b;
scanf("%d",&b);
if(b==0){
a=0;
}
elseif(b==1||b==2){
a=5;
}
elseif(b==3||b==4){
a=8;
}
elseif(b==5||b==6){
a=11;
}
elseif(b==7||b==8||b==9){
a=13;
}
elseif(b==10||b==11){
a=15;
}
elseif(b==12||b==13||b==14){
a=17;
}
elseif(b>=15){
a=18;
}
printf("%d\n",a );
return0;
}
发表于 2023-06-09 21:16:29
回复(0)
import java.util.*;
public class Main {
public static void main(String []args){
Scanner in=new Scanner(System.in);
int N=in.nextInt();
int num=0;
if(N>=1){
num+=5;
if(N>=3){
num+=3;
if(N>=5){
num+=3;
if(N>=7){
num+=2;
if(N>=10){
num+=2;
if(N>=12){
num+=2;
if(N>=15){
num+=1;
}}}}}}}
System.out.println(num);
}
public class Main {
public static void main(String []args){
Scanner in=new Scanner(System.in);
int N=in.nextInt();
int num=0;
if(N>=1){
num+=5;
if(N>=3){
num+=3;
if(N>=5){
num+=3;
if(N>=7){
num+=2;
if(N>=10){
num+=2;
if(N>=12){
num+=2;
if(N>=15){
num+=1;
}}}}}}}
System.out.println(num);
}
}
新手代码，哈哈哈
发表于 2022-10-05 20:57:02
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(); // 相当于容量为n的背包
int[] a = {2,3,1,5,4,3}; // 口罩数量（物品价格）
int[] b = {2,2,3,1,5,2}; // 口罩价格（物品重量）
// 01背包问题变形,将b装入n容量的背包，最大价值
int[] dp = new int[n + 1];
// 一维dp，一定是先遍历物品（b数组），再倒序遍历背包（n）
for (int i = 0; i < b.length; i++) {
for (int j = n; j >= b[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - b[i]] + a[i]);
}
}
System.out.println(dp[n]);
}
}
发表于 2022-08-24 18:26:05
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner input = new Scanner(System.in);
int n =input.nextInt();
int[] a = {0,2,3,1,5,4,3}; // 口罩数量
int[] b = {0,2,2,3,1,5,2}; // 口罩价格
// 7表示的是0-6六种口罩，n+1表示的是一共有0-n元钱
int[][] dp = new int[7][n + 1];
dp[0][0] = 0;
for (int i = 1; i <= 6; i++) { // 遍历口罩数量
for (int j = 1; j <= n; j++) { // 遍历钱数
// 当前的剩余钱数j是否买得起口罩i
if (j < b[i]) {
// 第一种情况:钱不够
dp[i][j] = dp[i - 1][j];
} else {
// 第二种情况: 买得起
// 继续判断是否买第i个, 分两种情况
// 1. 不买, 此时口罩最大数量和 i-1 情况一样, 即 dp[i][j] = dp[i - 1][j]
// 2. 买, 此时的最大数量时第 i-1 种口罩的数量加上第 i 种口罩的数量, 即 dp[i - 1][j - b[i]] + a[i]
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - b[i]] + a[i]);
}
}
}
System.out.println(dp[6][n]);
}
}
发表于 2022-08-14 12:06:18
回复(0)
01背包问题
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner in =new Scanner(System.in);
int n= in.nextInt();//输入N元钱，相当于背包总容量
int[] prices={0,2,2,3,1,5,2};//每种口罩的价格，相当于每个占用背包的容量
int[] number={0,2,3,1,5,4,3};//买一份有多少个口罩，相当于背包问题的价值
int[][] dp=new int[7][n+1];//初始化一个二维数组dp，用来存放最大价值。int[7][n+1] 7表示的是0-6六种口罩，n+1表示的是一共有0-n元钱（背包容量）
int max=0;
for (int i = 0; i <n+1 ; i++) {//当一种口罩不买时，不管钱多少，口罩数量均为0
dp[0][i]=0;
}
for (int i = 1; i <7 ; i++) {//控制遍历口罩的序号（商品序号）
for (int j = 0; j <n+1; j++) {//控制遍历钱数（空间大小）
if (j>=prices[i]){
//如果当前的钱数j买得起当前的口罩i，那么有两种选择，
// 1：不买当前的口罩（不装入背包），此时的最大数量和第i-1种口罩的数量一致
// 2：购买当前的口罩（装入背包），此时的最大数量时第i-1种口罩的数量加上第i种口罩的数量，
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-prices[i]]+number[i]);
}else { //如果当前的钱数j买不起当前的口罩i，那么最大数量和第i-1种口罩一致
dp[i][j]=dp[i-1][j];
}
max=dp[i][j];
}
}
System.out.println(max);
}
}
public class Main{
public static void main(String[] args) {
Scanner in =new Scanner(System.in);
int n= in.nextInt();//输入N元钱，相当于背包总容量
int[] prices={0,2,2,3,1,5,2};//每种口罩的价格，相当于每个占用背包的容量
int[] number={0,2,3,1,5,4,3};//买一份有多少个口罩，相当于背包问题的价值
int[][] dp=new int[7][n+1];//初始化一个二维数组dp，用来存放最大价值。int[7][n+1] 7表示的是0-6六种口罩，n+1表示的是一共有0-n元钱（背包容量）
int max=0;
for (int i = 0; i <n+1 ; i++) {//当一种口罩不买时，不管钱多少，口罩数量均为0
dp[0][i]=0;
}
for (int i = 1; i <7 ; i++) {//控制遍历口罩的序号（商品序号）
for (int j = 0; j <n+1; j++) {//控制遍历钱数（空间大小）
if (j>=prices[i]){
//如果当前的钱数j买得起当前的口罩i，那么有两种选择，
// 1：不买当前的口罩（不装入背包），此时的最大数量和第i-1种口罩的数量一致
// 2：购买当前的口罩（装入背包），此时的最大数量时第i-1种口罩的数量加上第i种口罩的数量，
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-prices[i]]+number[i]);
}else { //如果当前的钱数j买不起当前的口罩i，那么最大数量和第i-1种口罩一致
dp[i][j]=dp[i-1][j];
}
max=dp[i][j];
}
}
System.out.println(max);
}
}
发表于 2021-10-16 11:13:04
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[][] brand = {{0,0},{2,2},{3,2},{1,3},{5,1},{4,5},{3,2}};
int money = in.nextInt();
int[][] dp = new int[7][money+1];
dp[0][1] = 0;
for(int i = 1; i <= 6; i++){
for(int j = 1; j <= money; j++){
if(j-brand[i][1] >= 0)
// dp[i-1][j],没有第i种口罩时，能买的最大数量
// brand[i][0] + dp[i-1][j-brand[i][1]],买了当前口罩 + 剩余钱能买的最大数量
dp[i][j] =Math.max(dp[i-1][j],brand[i][0] + dp[i-1][j-brand[i][1]]);
else
// 钱不够买当前口罩
dp[i][j] =dp[i-1][j];
}
}
System.out.println(dp[6][money]);
}
}
编辑于 2021-08-07 11:29:07
回复(0)
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int N;
cin>>N;
vector<int> dp(N+1,0);
int m[] = {2, 2, 3, 1, 5, 2};
int c[] = {2, 3, 1, 5, 4, 3};
for(int i = 1; i <= N; ++i)
{
for(int j = N; j >= m[i]; --j)
{
dp[j] = max(dp[j],dp[j-v[i]]+c[i]);//动态规划解决
}
}
cout<<dp[N];
return 0;
}
把它完全按照动态规划的思路去想去做
发表于 2021-08-06 16:46:44
回复(0)
N=int(input().strip()) P=[[5,1],[3,2],[3,2],[4,5],[2,2],[1,3]] #[number,price] c=0 while N>=2 and len(P)!=0: i=0 f=0 while i<len(P): if P[i][1]<=N: c+=P[i][0] N-=P[i][1] del P[i] f=1 break i=i+1 if f==0:break print(c)
发表于 2021-06-04 10:59:15
回复(0)
n=int(input())
# 字典的键值要求是唯一的
sales={1:(5,1),2:(3,2),3:(3,2),4:(2,2),5:(4,5),6:(1,3)}
#print(len(sales))
def buy(n):
res=0
for k, v in sales.items():
if(n-v[1]>=0 and k<4):
res=res+v[0]
n-=v[1]
elif(n>=10 and k==4):
res=res+7
break
elif(n>=7 and k==4):
res=res+6
break
elif(n>=5 and k==4):
res=res+4
break
elif(n>=2 and k==4):
res=res+2
break
print(res)
buy(n)
发表于 2021-03-29 15:53:57
回复(0)
先把各品牌口罩的个数与价钱的比值进行排序，从前到后依次购买。顺序是DBFAEC。
10~11块钱的情况特殊，买完D、B、F剩余5元，再花2元买A的2个就无法再买，不如花5元买E的4个。
于是，设定余额不低于5元且不高于6元时，跳过A而选择E。
发表于 2021-03-20 18:04:46
回复(0)
问题信息
通过挑战的用户
-
2023-03-05 14:44:01
-
2023-01-03 16:17:11 -
2022-12-18 19:54:51 -
2022-11-05 21:24:17 -
2022-11-01 12:13:51
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
