首页 > 试题广场 >

买苹果

[编程题]买苹果
  • 热度指数：27935 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
小易去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装(包装不可拆分)。 可是小易现在只想购买恰好n个苹果，小易想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果，小易将不会购买。

输入描述:
输入一个整数n，表示小易想购买n(1 ≤ n ≤ 100)个苹果


输出描述:
输出一个整数表示最少需要购买的袋数，如果不能买恰好n个苹果则输出-1
示例1

输入

20

输出

3
算法知识视频讲解
添加回答
Python
DJy201807201027569头像 DJy201807201027569
完全不用DP这么复杂的，因为题目最大数只有100所以直接找出所有100以内符合的数做对应的最小的组合数即可。
1，如果全用6或者8即最多17*6和13*8，所以循环17个6与13个8进行组合
2，定义字典res{}，K为复合要求的苹果总数，V为此K下最小的组合数，发现res中K已经存在则判断当前下的V与之前存储的V取最小值更新，否则直接存储
3，输出先判断是否在K中，再直接输出对应的V，否则输出-1即可 

import sys
N=int(input())
res={}
for i in range(0,17):
    for j in range(0,13):
        a=i*6+j*8
        if(1<=a<=100):
            if(a)in res.keys():res[a]=min(res[a],i+j)
            else:res[a]=i+j
if N in res.keys():print(res[N])
else:print(-1)


发表于 2018-08-26 10:57:36 回复(0)
Python
半夏半暖头像 半夏半暖
n = int(input())
result = []
for i in range(n//8+1):
    for j in range(n//6+1):
        if 8*i + 6*j == n:
            result.append(i+j)
if len(result) == 0:
    print(-1)
else:
    print(min(result))

发表于 2018-07-31 11:51:55 回复(0)
Python
麻瓜工程师头像 麻瓜工程师
典型的动态规划题目，代码写得很丑 
n = int(input())
dp = [float('inf')] * (n+1)
if n+1 > 6:
    dp[6] = 1
if n+1 > 8:
    dp[8] = 1
for i in range(n+1):
    if i + 6 <= n:
        if dp[i+6] > dp[i] + 1:
            dp[i + 6] = dp[i] + 1
    if i + 8 <= n:
        if dp[i + 8] > dp[i] + 1:
            dp[i + 8] = dp[i] + 1
print(dp[n] if dp[n] != float('inf') else -1)

发表于 2018-07-11 23:02:43 回复(0)
Python
离疏头像 离疏 
n=int(input())

if n%8==0:
    ans=int(n/8)
else:
    a=n//8
    while a>=0:
        temp=n-a*8
        if temp%6==0:
            b=temp/6
            ans=int(a+b)
            break
        else:
            a-=1
    if a==-1:
        ans=-1
print(ans)

发表于 2018-04-24 11:28:57 回复(0)
Python
华科平凡头像 华科平凡

python 解法：

这道题还用什么动态规划啊。直接暴力求解多省事

def calcMinimumBags(number):
    for i in range(number // 6 + 1):
        if (number - i * 6) % 8 == 0:
            return i + (number - i * 6) // 8
    return -1
print(calcMinimumBags(int(input())))
发表于 2018-04-12 16:07:22 回复(3)
Python
Y_XY头像 Y_XY
#初学者的笨方法
#能买的苹果个数：6,8,12,14,16，....除6和8外都是大于等于12的偶数
while True:
    try:
        n=int(raw_input())
        if n==6 or n==8:
            m=1
            print m
        elif n>=12 and n%2==0:
            m1=n/8
            while (n-8*m1)%6!=0:
                m1=m1-1
            m2=(n-8*m1)/6
            m=m1+m2
            print m
        else:
            m=-1
            print m
    except:
        break

发表于 2018-03-31 22:07:13 回复(0)
Python
RWI头像 RWI 
n=int(raw_input())
if n%8==0:
    print n/8
elif n%8==6:
    print n/8+1
elif n%8==4:
    if n/8>=1:
        print n/8+1
    else:
        print -1
elif n%8==2:
    if n/8>=2:
        print n/8+1
    else:
        print -1
else:
    print -1

发表于 2017-12-26 10:42:45 回复(0)
Python
nullhh头像 nullhh 
#SB系统，TM一直以为不需要输入
def coinChange(coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp = [amount+1]*(amount+1)
        dp[0] = 0
         
        fori in range(amount+1):
            forc in coins:
                ifc<=i:
                    dp[i]=min(dp[i],dp[i-c]+1)
                     
        return-1ifdp[amount]==amount+1elsedp[amount]
n = int(raw_input().strip())
print coinChange([6,8], n)

编辑于 2017-08-12 23:26:58 回复(0)
Python
Traveling Light头像 Traveling Light 
if __name__ == "__main__":
    a = raw_input()
    a = int(a)
    min_ = 100
    times = 0
    for i in range(a / 8 + 1):
        rest = a - i * 8            
        if(rest % 6 == 0):
            times = i + rest /6
            min_ = min(times,min_)
    if min_ == 100:
        print -1
    else:
        print min_
稍做分析发现 6 和 8比较特殊，大于10的偶数都能够满足要求
编辑于 2016-09-25 17:13:08 回复(0)
Python
蒲公英_23头像 蒲公英_23 
num=raw_input('')
num=int(num)
if(num%2!=0 or num<6 or num==10):
    print '-1'
elif(num%8==0):
    print num/8
else:
    print 1+num/8

发表于 2016-09-21 18:47:25 回复(0)
提交观点

问题信息

贪心 动态规划 数学
来自：网易2017秋招编程题集合
难度：
10条回答 25307浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号