首页 > 试题广场 >

最少数量货物装箱问题

[编程题]最少数量货物装箱问题
  • 热度指数：8904 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
有重量分别为 3，5，7 公斤的三种货物，和一个载重量为 X 公斤的箱子（不考虑体积等其它因素，只计算重量）
需要向箱子内装满X公斤的货物，要求使用的货物个数尽可能少（三种货物数量无限）

数据范围：

输入描述:
输入箱子载重量(一个整数)。


输出描述:
如果无法装满，输出 -1。
如果可以装满，输出使用货物的总个数。
示例1

输入

4

输出

-1

说明

无法装满
示例2

输入

8

输出

2

说明

使用1个5公斤，1个3公斤货物
算法知识视频讲解
添加回答
Python
王子的诱惑头像 王子的诱惑 
递归
#coding=utf-8
def k5(n):#对于5与3的分配
    d,f,r=n%5,1,n//5#对n取余
    while d%3!=0:#如果余数是3的倍数就可以组合
        d+=5#如果不是就加5
        r-=1
        if d>n:#直到超过n那就说明不能组合
            f=0
            return -1
            break
    if f:
        return d//3+r#d//3是3个数，r是5的个数
            
def k7(n):#对于7与（5&3）的分配
    d,f,re=n%7,1,n//7#对n取余
    while k5(d)==-1:#如果余数是可以用3与5组合，那么就成立
        d+=7#不能组合就加7
        re-=1
        if d>n:#超过时候不能成立
            f=0
            return -1
            break
    if f:
        return k5(d)+re#k5(d)是5与3组合后总数，re是7的个数

while 1:
    try:
        x=int(input())
        print(k7(x))
    except:
        break

发表于 2020-08-17 10:59:34 回复(0)
Python
欧巴禾头像 欧巴禾
def f(n):
    dp = [0]*10000
    dp[1] = -1
    dp[2] = -1
    dp[3] = 1
    dp[4] = -1
    dp[5] = 1
    dp[6] = 2
    dp[7] = 1
    dp[8] = 2
    dp[9] = 3
    dp[10] = 2
    dp[11] = 3
    if n<=10:
        return dp[n]
    else:
        for i in range(12, n+1, 1):
            dp[i] = min(dp[i-7]+1,
                        dp[i-5]+1,
                        dp[i-3]+1)
        return dp[n]
while True:
    try:
        n = int(input())
        print(f(n))
    except:
        break
发表于 2019-08-09 11:16:10 回复(0)
提交观点

问题信息

C++工程师 贪心 动态规划 快手 2019 游戏研发工程师 Java工程师
上传者：小小
难度：
2条回答 9253浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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