首页 > 试题广场 >

买口罩

[编程题]买口罩

热度指数：2180 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小明有N元钱去药店买口罩，药店里有6个品牌的口罩，A品牌2个装（2元），B品牌3个装（2元）、C品牌1个装（3元）、D品牌5个装（1元），E品牌4个装（5元），F品牌3个装（2元），由于限购每个品牌最多只能买一个，小明最多能买多少口罩？

输入描述:

N元钱（1

输出描述:

N元钱能买到的口罩数目

示例1

输入

输出

算法知识视频讲解

你都不肯叫我一声教父

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)

theyi

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])

发表于 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)

C/C++

不写作的李华

#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);
      }

}

新手代码，哈哈哈

发表于 2022-10-05 20:57:02 回复(0)

牛客123018470号

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)

牛客791886300号

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);
}
}

具体思路：
https://blog.csdn.net/Supremey/article/details/120785736

发表于 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)

论如何收获offer

#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)

Python

maoxiaomao

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)

牛客623221513号

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)