用Python写了个函数，解决酒瓶换酒的问题，求大牛们指点？（问题已解决，感谢各位！）

01-16

问题描述：
一瓶酒两元钱，两个酒瓶可以换一瓶酒，四个瓶盖可以换一瓶酒，现在有N元钱，求最多可以买多少瓶酒？
作者：@zzzxs
def ryan(n) : jiu = n / 2 ping = jiu gai = jiu if jiu == 0: return 0 else: while ping / 2 &> 0 or gai / 4 &> 0: if ping / 2 &> 0: tmp = ping/2 jiu = jiu + tmp gai = gai + tmp ping = ping % 2 ping += tmp elif gai / 4 &> 0 : tmp = gai / 4 jiu = jiu + tmp ping = ping + tmp gai = gai % 4 gai += tmp return jiu

-----
上述代码来自@zzzxs的修改，感激不尽！！^_^

----
无意中在知乎上看到这个问题，很感兴趣，就动手用python写了下。
请问各位算法大牛，我写的这个函数，是否正确？
谢谢！

这种题目，是要看假设的。题目问最多，很重要的一点在于，能不能向老板借瓶子和盖子。如果不能借，上面的几位已经写好code了。我补充一点，如果能借的时候，有两种原子操作：

1、已有一个瓶子时，借一个瓶子，兑换之后喝，喝完还掉瓶子，净效果是消耗一个瓶子，获得一个瓶盖 + 一份酒。

2、已有两个盖子，借2个盖，换一瓶酒，喝完剩一瓶一盖，使用操作1，又喝一份酒，剩两个盖子，还掉这两个盖子。净效果：两个盖子，完整消耗，然后喝了两份酒。

使用这两种操作，可以得到比不能借的情况下更优的解。因此，整个code就会变成这样：

def drink(n):


    tot = 0
    wine, bottle, lid = n/2,0,0
    while True:

        if wine!=0:

            tot+=wine

            bottle+=wine

            lid+=wine

            wine=0

        elif bottle!=0:

            tot+=bottle

            lid+=bottle

            bottle=0

        elif lid &>= 2:

            tot+= (lid/2)*2

            lid%=2

        else:

            break
    return tot

print drink(10)

这样结果就会得到理论上的喝了20瓶酒的结果了。

@白如冰老白说：如果能借的话，岂不是先借他一两百瓶喝一喝（喝完了就跑真刺激

请先看这个百度知道：啤酒2元一瓶，每2个空的酒瓶能换1瓶酒，没4个瓶盖能换1瓶酒，假设现有10元，一共能喝多少瓶酒

题主代码错误太显然，其他人早指出了，这个我就不重复说了。

但这不是关键问题啊，关键问题是，怎么证明题主的做法一定是对的？

比如10块钱，一开始10块钱 = 5份酒 + 5个瓶 + 5个盖（简称为5 5 5），在题主的代码中，下一步一定是6 4 6，这个先考虑瓶，再考虑盖的贪心策略，是否一定正确呢？

换句话说，下一步 6 4 6 和 6 6 2，是否最后都能得到 15 1 3？还是有更优解？

很惭愧，我数学功底有限。不过我可以用代码搜索所有中间过程，并画图：

根据题意，显然只需考虑偶数：

2元钱

4元钱

6元钱

8元钱

10元钱

12元钱

总结下来几条性质：

1. 两元可以换到 1 1 1，k元（k为&>=4的偶数）可以换到 2k-5 1 3

2. 无论怎么兑换，都是百川归海，答案唯一

3. 上面的图，是下面的图的子图（参考10元从5 5 5开始，和12元从9 5 5开始，9-5=4，刚好2元=4份酒）我只能做到这里，希望有人能严格证明一下：在换酒问题中，无论中间过程如何，都能得到最优的唯一答案。

确实 … 如 @zzzxs 所言，题主的循环中少处理了“用盖子换酒时也会再得到盖子”与“用酒瓶换酒时也会再得到酒瓶”两个事件 …

所以题主的循环中，用盖子换酒，换来的是一瓶没有盖子的酒；用酒瓶换酒，换来的只有盖子和酒 …

我来贴和 @zzzxs 几乎一样的程序，只是变量名不同 …

$ cat a.py def wine(n): wine = n / 2; cap = wine; bottle = wine; while True: if cap &>= 4: delta = cap / 4; wine = wine + delta; bottle = bottle + delta; cap = cap + delta; cap = cap - delta * 4; if bottle &>= 2: delta = bottle / 2; wine = wine + delta; bottle = bottle + delta; cap = cap + delta; bottle = bottle - delta * 2; if bottle &< 2 and cap &< 4: break return wine; print wine(10)

运行时候是这样的：

$ python a.py 15

这个题目实质上是一个动态规划的问题（以下讨论限于不能向老板借瓶盖和瓶子的情形）。但也可以利用规律一步计算得到结果。

设最开始可以一次性购买y瓶酒（连同y个瓶子和y个瓶盖），之后剩余的钱其实和问题无关了，那么初始状态可以设为元组(y, y, y)；

之后，我们有两种兑换可能，一种是兑换瓶子，一种是兑换瓶盖。每次兑换就是发生了一次状态转移。结合状态转移后的最优子结构性质（每次兑换使得喝到的酒严格增加），我们选择对应结果更优的兑换，可以列出代码：

def drink(y):


    def trans(y, b, c):

        if b &< 0 or c &< 0:
            return -float("inf"), None, None
        if b &< 2 and c &< 4:
            return y, b, c
        else:
            n1 = trans(y+1, b-1, c+1)
            n2 = trans(y+1, b+1, c-3)
            if n1[0] &> n2[0]:

                return n1

            else:

                return n2

return trans(y, y, y)

问题得解。这个方法效率很低，但严谨性得以保证（类似的可以参考背包问题和钱币的兑换问题）。

-----------------分-----割-----线--------------------

但是我们直觉上不论怎样兑换，都会有一致的结果，所以可以使用循环而非递归的方法来求解。如 @Zack 童鞋所说，我们该如何证明这种策略不影响其最优解性质呢？

设最初可以买 $y_0$ 瓶酒，下面证明最终能喝到的酒 $y$ （以瓶为单位）为：

$y = egin{cases} 1, y_0 = 1 \ 4y_0-5, y_0> 1<br /> end{cases}$

证明：

设任意时刻的状态为 $(y, b, c)$ ，其中 $y$ 代表该时刻已喝到的酒， $b$ 代表该时刻的瓶子数， $c$ 代表该时刻的瓶盖数。

- 当 $y_0=1$ ， $(1, 1, 1)$ 即是最终状态；

- 当 $y_0=2$ ，有最优兑换过程 $(2, 2, 2) o (3,1,3)$ ；

- 当 $y_0>2$ ，我们设先买两瓶并采用最优兑换得 $(3,1,3)$ ，此后每买一瓶，都立即着手兑换并可以再喝到4瓶，且一定余下1个空瓶和3个瓶盖。设y为任意时刻喝到的酒，再买一瓶并进行兑换具体过程为：

$egin{align} ; (y,1,3)+(1,1,1) \ = ; (y+1,2,4) \ o ; (y+2,1,5) \ o ; (y+3,2,2) \ o ; (y+4,1,3) end{align}$

递推可得 $y_0geq 2$ 情形下的通项为 $left( 4(y_0-2) + 3, 1, 3 ight)=(4y_0-5, 1, 3)$ 。

然后利用归纳法证明最优性质。假设买酒和兑换的最优解符合上述递推规律，则给定任意初始状态 $(y,y,y)$ ，分两次买酒，分别兑换再合并，则该状态可以分解为：

- $(y-1,y-1,y-1)+(1,1,1)$ 即逐瓶购买的情形，即上述递推；

- $(y_1,y_1,y_1) + (y_2,y_2,y_2)$ 的情形，此时利用归纳假设，结合两个子结构的最优解 $(4y_1-5,1,3)+(4y_2-5,1,3)=(4y-10, 2, 6) o... o (4y-5,1,3)$ ，仍然符合递推规律。

（注意这里的状态转移和分割线前的版本不相同，仅作证明方便考虑）。

综上证毕。

--------

所以程序可以两句话写完（雾

def drink0(N): y = N // 2 return 4 * y - 5 if y &> 1 else 0

题主没有考虑全啊……毕竟小学奥数题里就有可以借钱嘛……

Q：代码是否正确

A：不正确，因为你没考虑买酒以后瓶子盖子都会增加。

看看代码假装不给借的话，那么这样贪心换酒的策略已经被前面答案证明了，不过嘛

def drink0(N): return 4 * (N//2) - 5

你的代码和证明很漂亮，就是有没有考略N&<=3的情况啊→ →

@Lee Shellay

蛮有意思的mark一下

def get_bot_conunt(n): return bottles(0,n/2,0,0)


def bottles(had,wine,bott,top):

    if wine == 0:

        return had

    had +=wine

    bott +=wine

    top +=wine
    wine = 0
    wine += (bott/2)

    wine += (top/4)
    bott = bott%2

    top = top%4

    return bottles(had,wine,bott,top)

print get_bot_conunt(10)

我用递归的写法得出的结果跟你的不一样。

我测了下 6块钱的时候就开始不一样了。

我发现你漏加了东西

把你的代码修改了一下

def ryan(n) : jiu = n / 2 ping = jiu gai = jiu if jiu == 0: return 0 else: while ping / 2 &> 0 or gai / 4 &> 0: if ping / 2 &> 0: tmp = ping/2 jiu = jiu + tmp gai = gai + tmp ping = ping % 2 ping += tmp elif gai / 4 &> 0 : tmp = gai / 4 jiu = jiu + tmp ping = ping + tmp gai = gai % 4 gai += tmp return jiu

这个问题最后的本质是等比数列求和

你的答案应该是错的，显然这里两块钱买的一瓶酒包括瓶子，盖子，和酒，最后问的买多少瓶酒不包括瓶子和盖子。于是可得到

4G=2P=1P+1G+1J=2计算可得到J=0.5，即一瓶酒不包括瓶子和盖子是五毛钱，10块钱可以买20瓶酒。

一瓶酒两元钱，两个酒瓶可以换一瓶酒，四个瓶盖可以换一瓶酒

相当于一个酒瓶1元，一个瓶盖0.5元，也就是说光酒的价格是0.5元。

如果可以借瓶借瓶盖的话，最多可买N/0.5瓶=2N瓶。

你们没发现只能用两元买一瓶酒，剩下的都是换酒么

我觉得题主最好把什么jiu啊ping啊的换成英文好一些。。乍眼一看jiu我都没反应过来是什么单词。。

如果能赊账,酒瓶值1块，瓶盖值五毛，酒本身值五毛，N元可以喝2N瓶。

你瓶的计算错了，应该是ping=ping/2+ping%1(高效的是ping=(ping+1)/2)，同理

行为树。。。。。。。。

怎么现在各种出身开始当码农了

生活的问题，拿钱一试便出结果；

搬到计算机上，就需要找规律了....

而这规律总结起来，有3个重点。

第一、开始，N元钱可以买N瓶酒；

第二、结束，喝完最后一瓶酒时，剩下的瓶盖和酒瓶，肯定不能再凑够数拿去换的；

第三、每一次得到酒，要喝完，剩下的瓶盖和酒瓶才能够拿去兑换酒

这是第一版的，考虑了1和2，但是没把3考虑完， def Drink(_rmb): num = 0 #总酒数 wine = _rmb/2 #当前酒数 while (wine!=0): # 还有酒喝酒继续 num += wine #更新总酒数 temp = wine #临时保存 wine = 0 #表示酒喝完了，无意义，可删掉 wine = temp/2 + temp/4 # 拿瓶和盖去换酒 return num print Drink(10)


第二版，每一次换酒，都要把当前的瓶和盖的剩余量记下来，放入下一次运算

def Drink(_rmb):

    num = 0 #总酒数

    wine = _rmb/2 #当前酒数

    remain_bottle = 0 #剩余0个瓶

    remain_cap = 0    #剩余0个盖

    while (wine!=0): # 还有酒喝酒继续

        num += wine #更新总酒数

        temp = wine #temp保存这一次换回来的酒

        wine = (temp+remain_bottle)/2 + (temp+remain_cap)/4 # 拿所有的瓶和盖去换酒

        remain_bottle = (temp+remain_bottle)%2 #余下的瓶

        remain_cap = (temp+remain_cap)%4 #余下的盖

    return num

print Drink(10) 代码源于生活，生活还是生活这样快一点

不得不说

在这种题目给定的条件里就隐含了一个核心：

一瓶酒，酒水，瓶子，瓶盖都带有了货币属性。

赊一瓶酒。实际是，贷款了。

贷款包括，一酒水，一瓶子，一盖子。

瓶子，盖子不属于你。

不能再拿瓶子，盖子去换一整瓶酒。再清楚地说一次。

好比贷款总共A

其中包括A1酒A2瓶子A3盖子。

先贷款A，

然后拿其中的A2和A3再去换取（贷款）A，

然后拿这次的A去还上次的A。

然后就不欠款了？？

合理吗？

当然需要酒馆老板配合咯，

因为他除非脑袋被门夹了。

银行要接受这思路，早隔屁了。

实在看不下去了。

…………………………

记住，

一，货币属性。

二，瓶子，盖子不属于你，你得还。

哎。

这就是为什么有的程序猿永远是码农的原因。