小雨去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装(包装不可拆分)。 可是小雨现在只想购买恰好n个苹果，小雨想购买尽量少的袋数方便携带。

看到的某道面试题：小雨去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装(包装不可拆分)。 可是小雨现在只想购买恰好n个苹果，小雨想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果，小雨将不会购买。
网上好多动态规划、回溯算法的解法，这里用纯数学解。
本题难点主要是：尽量少的袋数。

def buyApple(n):
    if n%2:
        return -1
    x = n%6 # 对6取余，余数只能是2和4
    x //= 2 # 计算余数有多少个2
    y = n//6 # 整数6
    if x > y:
        return -1
    else: # 当x <= y的时候，肯定可以购买，比如20: 6+6+6 余2 就成了 6+6+8了
    #     return y
    # 但是题目要求的是“最少”，这时候就要判断，是否有4个6存在，如果有，转为3个8 中间差了1 所以要减
        return y - (y-x)//4

if __name__ == '__main__':
    for i in range(1, 50):
        print("i:",2*i,"  res:",buyApple(2*i))

i: 2 res: -1
i: 4 res: -1
i: 6 res: 1
i: 8 res: 1
i: 10 res: -1
i: 12 res: 2
i: 14 res: 2
i: 16 res: 2
i: 18 res: 3
i: 20 res: 3
i: 22 res: 3
i: 24 res: 3
i: 26 res: 4
部分结果，测试好像都对，O(1)的时间复杂度。
看到结果想到一句话：任何大于3的整数，都可以由m个2，和n个3相加得到。
这里，感觉任何大于6的数，都可以由m个3和n个4组成，不知道对不对。

最后

以上就是害羞汽车为你收集整理的小雨去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装(包装不可拆分)。 可是小雨现在只想购买恰好n个苹果，小雨想购买尽量少的袋数方便携带。的全部内容，希望文章能够帮你解决小雨去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装(包装不可拆分)。 可是小雨现在只想购买恰好n个苹果，小雨想购买尽量少的袋数方便携带。所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。