会员卡每次只能充值 6000
商家项目有:
2880 (每次)
2380 (每次)
目前会员卡余额为 1720
请问要如何充值、如何消费才能把会员卡余额变为 0 ?
问题来源于生活,纯属娱乐,开拓思维
1
linhuoqi 2020-06-16 14:29:35 +08:00
1720 + x * 6000 == y * 2880 + z * 2380
是想找到最小的 x 吧 |
3
winmer 2020-06-16 15:09:37 +08:00
假设第一种消费 x 次 第二种消费 y 次 充值 n 次
有 6000n=2880x+2380y-1720 (x>-1 y>-1 n>1 x,y,n 为整数) 化简得 300n=144x+119y-860(x>-1 y>-1 n>1 x,y,n 为整数) 取 x=0 则问题转化为求解 y 使得 119y-860 能够整除 300 y 为整数 令 k=119y-860 若 k 满足 k=300n 则 k 个位为 0 乘 9 得 0 的整数只有 0 所以 y 个位为 0 k 十位也为 0 则 y 的十位上数字与 9 的乘积是 6 y 的十位为 4 令 y=40 时 k=119*40-860=3900 已经满足是 300 倍数的条件 接下来考虑 y 取更大值的可能 y=m*100+40 ( m 为非负整数)时 需满足 119*m 被 3 整除 已知 119 不是 3 的倍数 因此 m 是三的倍数 于是当 x=0 时,y 为 300M+40 即可满足上述条件 同理令 y=0 发现无法找到一个整数值 x 使得题目成立,因此 y=0 时 x>0 然后就可以在二维坐标轴上划出一个区域(令 m=x ) 在这个区域里随便搜搜或者暴力枚举...? |
4
gzfrankie 2020-06-16 15:14:51 +08:00
python 简单写了个 BFS 搜索
import queue q = queue.Queue() visited = set() def f(x,y,z): return 1720+6000*x-2880*y-2380*z def enqueueIfNotExist(try_solution): if try_solution not in visited: q.put(try_solution) visited.add(try_solution) def main(): q.put((0,0,0)) visited.add((0,0,0)) while not q.empty(): try_solution = q.get() x = try_solution[0] y = try_solution[1] z = try_solution[2] remain = f(x,y,z) print("x,y,z=",x,",",y,",",z," remain ",remain) if remain == 0: return try_solution elif remain > 0: try_solution = (x,y+1,z) enqueueIfNotExist(try_solution) try_solution = (x,y,z+1) enqueueIfNotExist(try_solution) elif remain < 0: try_solution = (x+1,y,z) enqueueIfNotExist(try_solution) if __name__=="__main__": main() 最后答案是 8,9,10,即 1720+6000*8-2880*9-2380*10=0 |
5
gzfrankie 2020-06-16 15:22:44 +08:00 1
贴上来格式乱了,传个在线 ide 的地址吧,ideone.com/sS9e5Z
|
6
gzfrankie 2020-06-16 15:41:09 +08:00 1
点进 ide 的页面能看到所有枚举过程,如果是想尽可能充少点钱的话,比较好的方法:
1,1,2 剩 80 3,6,1 剩 60 |
8
daniel1996 2020-06-16 18:45:51 +08:00
@gzfrankie 大佬大佬
|
10
realkun 2020-06-18 21:16:38 +08:00
真就技术成就美好生活啊
|