最少货物装箱问题

最少数量货物装箱问题

牛客网：货物装箱问题
题目描述python

有重量分别为3，5，7公斤的三种货物，和一个载重量为X公斤的箱子（不考虑体积等其它因素，只计算重量） 须要向箱子内装满 n 公斤的货物，要求使用的货物个数尽量少（三种货物数量无限）web

示例1算法

输入 4 输出 -1 说明：没法装满数组

示例2
输入 8 输出 2 说明：使用1个5公斤，1个3公斤货物svg

先上代码，直接计算给定的n便可。因为测试样例不少，这道题目考的是数学思惟，而不是什么遍历，动态规划之类的算法。若是用python的话，建议优先来考虑其数学规律，否则很容易超时。测试

n = int(input().strip())
num = (-1, -1, 1, -1, 1, 2, 1, 2, 3, 2, 3, 2, 3)
if n < 14:
    print(num[n-1])
else:
    count = n//7-1
    print(count+num[6+n%7])

思路：
前7个很特殊，当n是1，2时，不知足要求，只能输出-1；n是4也不知足要求，输出-1，当n是3，5，7时，输出1就能够。n是6时，两个3就能够知足载货要求。此时前7个已经讨论完毕。
接着咱们看超出单个最大载货量 7 时，有什么规律code

这里为何不列举13日后的呢？由于咱们的策略是优先考虑 7 公斤的货物，那么 8 到 13 的例子正好对应了与 7 取余的 6 种状况。好比若是给定 n 是 36，那么能够用 36//7=5 个7公斤的货物，此时余数是1，对应了8的这种状况，那咱们此时去掉一个 7 公斤重的货物，填补上一个 3 公斤和一个 5 公斤重的货物，那么最终的箱子数目就是 5 - 1 + 2 = 6.xml

注意：看完上表，咱们发现只要给定的 n 大于7，那么必定不会输出-1.ip

所以算法步骤：get

1. 判断 n 的大小，小于14的能够统一利用 num 数组输出箱子数目。
2. 大于14的，能够先计算7公斤箱子所需的最大数目，count = n // 7,而后对照上面的余数表，计算其数量num【6+count%7】
3. 最后输出 count + num【6+count%7】-1。减1的目的就像上面说的，去掉一个7公斤重的箱子，而后再思考对应的最小策略。
   最后输出答案便可。

记得验证一些特殊边值条件，防止小错误，好比14。