在金盆洗手游戏中，有两个玩家，A和B，金盆排列成一排，每个金盆里都有一些金币。玩家可以看到每个金罐里有多少金币，每个玩家可以交替轮换，玩家可以从队伍的任何一端挑选一个金罐。最后拥有较多金币的玩家就是赢家。目标是 "最大化 "A收集的金币数量，假设B也是 "最佳 "发挥，A开始游戏。
比如说 For example
Player Opponent
4, 6, 2, 3 3
4, 6, 2 4
6, 2 6
2 2
9 coins 6 coins
9枚硬币 6枚硬币
玩家 对手
6, 1, 4, 9, 8, 5 6
1, 4, 9, 8, 5 5
1, 4, 9, 8 8
1, 4, 9 9
1, 4 4
1 1
18 coins 15 coins
18枚硬币 15枚硬币
练习这个问题
我们的想法是，在明知对手是最优策略的情况下，找到一个使玩家获胜的最优策略。玩家对硬币[i...j]有两个选择，其中i和j分别表示行的前部和后部。
1. 如果玩家选择了前面的锅i，对手就只能从[i+1, j]中选择。
如果对手选择了前锅i+1，则重复选择[i+2, j]。
如果对手选择了后锅j，则重复进行[i+1, j-1]。
2. 如果棋手选择了后锅j，那么对手就只能从[i, j-1]中选择。
如果对手选择了前锅i，则递归为[i+1, j-1]。
如果对手选择了后边的锅j-1，则重复选择[i, j-2]。
由于对手是以最优化的方式进行游戏，他将试图使玩家的点数最小化，即对手将做出使玩家的硬币最少的选择。因此，我们可以递归地将问题定义为。
伪代码
| coin[i] (如果i = j)
optimalStrategy(i, j) = | max(coin[i], coin[j]) (if i + 1 = j)
| max (coin[i] + min(optimalStrategy(coin, i + 2, j),
optimalStrategy(coin, i + 1, j - 1)）。
coin[j] + min(optimalStrategy(coin, i + 1, j - 1),
optimalStrategy(coin, i, j - 2)))
# Recursive function to maximize the number of coins collected by a player,
# assuming that the opponent also plays optimally
def findMaxCoins(coin, i, j):
# base case: one pot left, only one choice possible
if i == j:
return coin[i]
# if we are left with only two pots, choose one with maximum coins
if i + 1 == j:
return max(coin[i], coin[j])
# if a player chooses front pot `i`, the opponent is left to choose from [i+1, j]
# 1. If the opponent chooses front pot `i+1`, recur for [i+2, j]
# 2. If the opponent chooses rear pot `j`, recur for [i+1, j-1]
start = coin[i] + min(findMaxCoins(coin, i + 2, j),
findMaxCoins(coin, i + 1, j - 1))
# if a player chooses rear pot `j`, the opponent is left to choose from [i, j-1]
# 1. If the opponent chooses front pot `i`, recur for [i+1, j-1]
# 2. If the opponent chooses rear pot `j-1`, recur for [i, j-2]
end = coin[j] + min(findMaxCoins(coin, i + 1, j - 1),
findMaxCoins(coin, i, j - 2))
# return the maximum of two choices
return max(start, end)
# Pots of gold game using dynamic programming
if __name__ == '__main__':
# pots of gold (even number) arranged in a line
coin = [4, 6, 2, 3]
print('The maximum coins collected by player is',
findMaxCoins(coin, 0, len(coin) - 1))
以下是上述方法的Python实现。
集装箱码头摆放货柜
一排摆放的货柜，每个货柜的编号头字母是大写的字母 A->Z
现在你要编写指令，搬运机器人调整货柜的位置，目标是货柜编号按照字母表的顺序摆放。你考虑到节能减排的需求，尽量做到搬运的次数最少。
例如：
'ECADBF'，字符串格式表示货柜摆放的位置，目标是调整为 'ABCDEF'
最佳的搬运方案是：
D, F不动 !
1、E和B 交换位置后，'BCADEF'
2、A和B 交换位置后，'ACBDEF'
2、C和B 交换位置后，'ABCDEF'
共搬运 3 次即可完成！
def swapcaseUP(start):
s = start
swap = {}
cunt = 1
while s != sorted(s):
sorder = sorted(start)
for i,c in enumerate(s):
if i == sorder.index(c):pass
else:
t = sorder.index(c)
s[t],s[i] = s[i], s[t] # 不能用 c ！！1
swap[cunt] = f"{chr(s[t])} <-> {chr(s[i])}"
cunt += 1
return len(swap),swap,''.join([chr(i) for i in s])
输出结果：
测试用例 >>>
start = 'ABCDEFGHIJK'
print(f' {start}:',swapcaseUP(start))
ABCDEFGHIJK: (0, {}, 'ABCDEFGHIJK')
start = 'ABCDEFGHIJK'[::-1]
print(f' {start}:',swapcaseUP(start))
KJIHGFEDCBA: (5, {1: 'K <-> A', 2: 'J <-> B', 3: 'I <-> C', 4: 'H <-> D', 5: 'G <-> E'}, 'ABCDEFGHIJK')
start = 'FCABDE'
print(f'{start}:',swapcaseUP(start))
FCABDE: (5, {1: 'F <-> E', 2: 'C <-> A', 3: 'B <-> A', 4: 'D <-> A', 5: 'E <-> A'}, 'ABCDEF')
start = 'FCADBE'
print(f' {start}:',swapcaseUP(start))
FCADBE: (4, {1: 'F <-> E', 2: 'C <-> A', 3: 'B <-> A', 4: 'E <-> A'}, 'ABCDEF')
start = 'ECADBF'
print(f' {start}:',swapcaseUP(start))
ECADBF: (3, {1: 'E <-> B', 2: 'C <-> A', 3: 'B <-> A'}, 'ABCDEF')
start = 'FEDCBA'
print(f' {start}:',swapcaseUP(start))
FEDCBA: (3, {1: 'F <-> A', 2: 'E <-> B', 3: 'D <-> C'}, 'ABCDEF')
start = 'FEDCBAGH'
print(f' {start}:',swapcaseUP(start))
FEDCBAGH: (3, {1: 'F <-> A', 2: 'E <-> B', 3: 'D <-> C'}, 'ABCDEFGH')
start = 'FEDCBAGHIJ'
print(f'{start}:',swapcaseUP(start))
FEDCBAGHIJ: (3, {1: 'F <-> A', 2: 'E <-> B', 3: 'D <-> C'}, 'ABCDEFGHIJ')
start = 'FEDCBAGHJI'
print(f' {start}:',swapcaseUP(start))
FEDCBAGHJI: (4, {1: 'F <-> A', 2: 'E <-> B', 3: 'D <-> C', 4: 'J <-> I'}, 'ABCDEFGHIJ')
start = 'FEDCBAHGJI'
print(f' {start}:',swapcaseUP(start))
FEDCBAHGJI: (5, {1: 'F <-> A', 2: 'E <-> B', 3: 'D <-> C', 4: 'H <-> G', 5: 'J <-> I'}, 'ABCDEFGHIJ')
start = 'FAJIHGKEDCB'
print(f' {start}:',swapcaseUP(start))
FAJIHGKEDCB: (7, {1: 'F <-> G', 2: 'A <-> G', 3: 'J <-> C', 4: 'I <-> D', 5: 'H <-> E', 6: 'K <-> B', 7: 'G <-> B'}, 'ABCDEFGHIJK')
start = 'DFAECIGBJH'
print(f' {start}:',swapcaseUP(start))
DFAECIGBJH: (7, {1: 'D <-> E', 2: 'F <-> I', 3: 'A <-> E', 4: 'C <-> E', 5: 'B <-> I', 6: 'J <-> H', 7: 'I <-> H'}, 'ABCDEFGHIJ')
start = 'CDABEKIHGJF'
print(f' {start}:',swapcaseUP(start))
CDABEKIHGJF: (4, {1: 'C <-> A', 2: 'D <-> B', 3: 'K <-> F', 4: 'I <-> G'}, 'ABCDEFGHIJK')
团购水果的分配任务
自发组织团购了一车新鲜水果，预约的货车运载量是5千公斤左右。在疫情期间，我将分给小区的100多家。数量需求不尽不同，还好经验丰富的供货商考虑到水果发放要尽量便捷，提供大小不同的包装袋密封好，到小区后不必打开包装，通过适当的几种包装的组合能够凑出订购的数量。这样做以来，不仅省去每一家称重的时间，也极大地缩短人员聚集的时间。
你作为程序员更容易想到一个办法，建议水果供货商将水果分为固定的几种若干斤的重量的包装，最终能保证每家来领水果的时候，无论订购了多少斤，一定能找到组合出每一家的水果需求量。同时不会剩下，如何做到看起来近乎不可能的事情，希望你能给出各种包装的数量。
策略
首先要准确量出 1 -> n,且 sum(1+ ... +n) <= 5000 less or above
找到某种规律组合，能够凑出上述任意数量的水果
每一种包装的数量确定
def evensplit(n):
total = 1
i = 1
bench = []
while total <= n:
bench.append(i)
total += i
i += 1
maxwgt = len(bin(bench[-1])[2:])
bins = [2**i for i in range(maxwgt+1)][::-1]
weights = dict(zip(bins,len(bins)*[0]))
for n in bench[::-1]:
for k,v in weights.items():
weights[k] += n//k
n = n % k
return total,bins,weights
n = 5000
print('total ',evensplit(n))
total (5051, [128, 64, 32, 16, 8, 4, 2, 1], {128: 0, 64: 37, 32: 37, 16: 48, 8: 48, 4: 49, 2: 50, 1: 50})
领取水果的分配包装
输入参数是领取的重量 n
def pick(n):
b = bin(n)[2:][::-1]
ans = [2**int(i) for i,e in enumerate(b) if e == '1']
return [f"{i} kg 一袋" for i in ans]
n = 10
print(pick(n))
n = 17
print(pick(n))
n = 50
print(pick(n))
n = 100
print(pick(n))
['2 kg 一袋', '8 kg 一袋']
['1 kg 一袋', '16 kg 一袋']
['2 kg 一袋', '16 kg 一袋', '32 kg 一袋']
['4 kg 一袋', '32 kg 一袋', '64 kg 一袋']
启发商家的包装从小到大可以采用 1，2，4，8，... ..kg的包装
当然上述例子假设每一家的需求数量都不同时，而且一整车货载重固定5000kg的约束条件下，批发水果的包装大小的组合数量分布。
进一步看实际遇到有顾客订购相同数量的需求，现在解决起来变得容易。只需稍微修改代码：
例如：有 5 人 购买 20kg，有 7 人购买 30kg
我们需要在总量不变的情况下，调整特定包装的数量。
#1 首先看要增加哪些包装
s = [(5,20),(7,30)]
def picknum(n):
b = bin(n)[2:][::-1]
ans = [2**int(i) for i,e in enumerate(b) if e == '1']
return ans
# 保持总量的情况下，减少哪些包装
def adjust(s,n):
n = n - sum([x*y for x,y in s])
wgt = evensplit(n)[2]
t = [(w[0],picknum(w[1])) for w in s]
for m in t:
for k,v in wgt.items():
for i in m[1]:
if i == k:
wgt[k] += m[0]
return wgt
s,n = [(5,20),(7,30)],5000
print(adjust(s,n))
{128: 0, 64: 34, 32: 34, 16: 60, 8: 55, 4: 60, 2: 55, 1: 49}
对比原包装方案：
{128: 0, 64: 37, 32: 37, 16: 48, 8: 48, 4: 49, 2: 50, 1: 50})
结论是：
64kg的包装减少 3 袋
32kg的包装增加 3 袋
16kg的包装增加 2 袋
8kg的包装增加 7 袋
4kg的包装增加 11 袋
2kg的包装增加 5 袋
1kg的包装减少 1 袋
春节抢红包
我在微信群里亲朋好友的孩子发红包，因为每个孩子都很在意收的红包会不会比其他孩子少，于是我选择没有选择随机红包，而是平均等分红包。
而我又不想有剩下的钱而退回来。考虑到有孩子会错过抢红包。我计算了以下最少要往红包里转账多少钱，才能保证：
无论最后有多少孩子来参与抢红包，都能保证每个孩子都能得到相同的金额，同时我又不会剩下的部分钱退回？（请放心保证至少有一个孩子参加抢红包）。
输入参数 num -> 微信群的人数
def redPacket(num):
n = 1
for i in range(num):
init = n
while n % (i+1):
n += init
return n
amount_of_kids = 5
print(f'{amount_of_kids}',redPacket(amount_of_kids))
5 60
amount_of_kids = 7
print(f'{amount_of_kids}',redPacket(amount_of_kids))
7 420
amount_of_kids = 10
print(f'{amount_of_kids}',redPacket(amount_of_kids))
10 2520
结论：
如果邀请5人，无论1-5之间的人数，至少要准备 60 元保证每个抢到相同的数量；
如果邀请10人，无论来1-10之间的人数，至少要准备 420 元保证抢到相同的数量；
如果邀请10人，无论来1-10之间的人数，至少要准备 2520 元保证抢到相同的数量；
网友评论