酒瓶与瓶盖换酒问题 - 10块钱可以喝多少瓶酒
前些日子有QQ好友发给我下面这个问题：
啤酒2块钱1瓶，4个盖换一瓶，2个空瓶换一瓶，问10块钱可以喝多少瓶。
当时没有时间算这个问题（其实就是懒得动笔和动脑子），但这几天又老想着这个问题，所以今天决定写段代码解决一下。
一开始，由于没把题目琢磨太明白，于是用了具有暴力色彩的递归方式去算这道题，考虑每一种交换顺序，Java代码如下：
import java.util.Stack;
public class Solution {
int countOfDrinked;
Stack
String logOutputMax = "";
int priceEachBottle = 2; //一瓶酒多少钱
int bottleCanChange = 2; //多少瓶子能换一瓶酒
int capCanChange = 4; //多少瓶盖能换一瓶酒
public int countOfDrink(int money) {
countOfDrinked = 0;
stackStep.clear();
logOutputMax = "";
calcMax(money, 0, 0, 0);
System.out.println(logOutputMax);
return countOfDrinked;
}
private void calcMax(int money, int bottle, int cap, int drinked) {
if (money >= priceEachBottle) {
String log = "";
log += "动作：买入啤酒, ";
log += "剩余金钱： " + (money - priceEachBottle) + ", ";
log += "剩余酒瓶：" + (bottle + 1) + ", ";
log += "剩余瓶盖：" + (cap + 1) + ", ";
log += "已喝啤酒：" + (drinked + 1);
stackStep.push(log);
calcMax(money - priceEachBottle, bottle + 1, cap + 1, drinked + 1);
stackStep.pop();
}
if (bottle >= bottleCanChange) {
String log = "";
log += "动作：酒瓶换酒, ";
log += "剩余金钱： " + (money) + ", ";
log += "剩余酒瓶：" + (bottle - bottleCanChange + 1) + ", ";
log += "剩余瓶盖：" + (cap + 1) + ", ";
log += "已喝啤酒：" + (drinked + 1);
stackStep.push(log);
calcMax(money, bottle - bottleCanChange + 1, cap + 1, drinked + 1);
stackStep.pop();
}
if (cap >= capCanChange) {
String log = "";
log += "动作：瓶盖换酒, ";
log += "剩余金钱： " + (money) + ", ";
log += "剩余酒瓶：" + (bottle + 1) + ", ";
log += "剩余瓶盖：" + (cap - capCanChange + 1) + ", ";
log += "已喝啤酒：" + (drinked + 1);
stackStep.push(log);
calcMax(money, bottle + 1, cap - capCanChange + 1, drinked + 1);
stackStep.pop();
}
if (money < 2 && bottle < 2 && cap < 4) {
if (drinked > countOfDrinked) {
countOfDrinked = drinked;
logOutputMax = String.join(";\n", stackStep);
}
}
}
}
创建一个Main函数，代码如下：
class DrinkingProblem {
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.countOfDrink(10));
}
}
输出结果如下：
动作：买入啤酒, 剩余金钱： 8, 剩余酒瓶：1, 剩余瓶盖：1, 已喝啤酒：1;
动作：买入啤酒, 剩余金钱： 6, 剩余酒瓶：2, 剩余瓶盖：2, 已喝啤酒：2;
动作：买入啤酒, 剩余金钱： 4, 剩余酒瓶：3, 剩余瓶盖：3, 已喝啤酒：3;
动作：买入啤酒, 剩余金钱： 2, 剩余酒瓶：4, 剩余瓶盖：4, 已喝啤酒：4;
动作：买入啤酒, 剩余金钱： 0, 剩余酒瓶：5, 剩余瓶盖：5, 已喝啤酒：5;
动作：酒瓶换酒, 剩余金钱： 0, 剩余酒瓶：4, 剩余瓶盖：6, 已喝啤酒：6;
动作：酒瓶换酒, 剩余金钱： 0, 剩余酒瓶：3, 剩余瓶盖：7, 已喝啤酒：7;
动作：酒瓶换酒, 剩余金钱： 0, 剩余酒瓶：2, 剩余瓶盖：8, 已喝啤酒：8;
动作：酒瓶换酒, 剩余金钱： 0, 剩余酒瓶：1, 剩余瓶盖：9, 已喝啤酒：9;
动作：瓶盖换酒, 剩余金钱： 0, 剩余酒瓶：2, 剩余瓶盖：6, 已喝啤酒：10;
动作：酒瓶换酒, 剩余金钱： 0, 剩余酒瓶：1, 剩余瓶盖：7, 已喝啤酒：11;
动作：瓶盖换酒, 剩余金钱： 0, 剩余酒瓶：2, 剩余瓶盖：4, 已喝啤酒：12;
动作：酒瓶换酒, 剩余金钱： 0, 剩余酒瓶：1, 剩余瓶盖：5, 已喝啤酒：13;
动作：瓶盖换酒, 剩余金钱： 0, 剩余酒瓶：2, 剩余瓶盖：2, 已喝啤酒：14;
动作：酒瓶换酒, 剩余金钱： 0, 剩余酒瓶：1, 剩余瓶盖：3, 已喝啤酒：15
15
通过观察输出结果并研究题目，我发现了下面几条规律：
1、两块钱可以转换成一瓶酒（含一个瓶和一个盖），这个过程是不可逆的，所以可以先把钱优先换成酒
2、两个酒瓶可以转换为一个酒瓶和一个瓶盖，四个瓶盖可以转换为一个酒瓶和一个瓶盖，酒瓶和瓶盖虽然存在着转换关系，但这种转换关系也是不可逆的，酒瓶和瓶盖都只会越换越少，并且无论交换顺序如何改变，从一个状态转到另一个状态所需花费的步骤数是一样的。
这就给上面方法的改进提供了空间，于是我新写了一个代码，发现代码运行的结果是一样的：
import java.util.LinkedList;
public class Solution {
LinkedList
int priceEachBottle = 2; //一瓶酒多少钱
int bottleCanChange = 2; //多少瓶子能换一瓶酒
int capCanChange = 4; //多少瓶盖能换一瓶酒
public int countOfDrink(int money) {
linkedList.clear();
calcMax(money, 0, 0, 0);
System.out.println(String.join(";\n", linkedList));
return linkedList.size();
}
private void calcMax(int money, int bottle, int cap, int drinked) {
while (money >= priceEachBottle) {
String log = "";
log += "动作：买入啤酒, ";
log += "剩余金钱： " + (money - priceEachBottle) + ", ";
log += "剩余酒瓶：" + (bottle + 1) + ", ";
log += "剩余瓶盖：" + (cap + 1) + ", ";
log += "已喝啤酒：" + (drinked + 1);
linkedList.addLast(log);
money -= priceEachBottle;
bottle++;
cap++;
drinked++;
}
while (true) {
if (bottle >= bottleCanChange) {
String log = "";
log += "动作：酒瓶换酒, ";
log += "剩余金钱： " + (money) + ", ";
log += "剩余酒瓶：" + (bottle - bottleCanChange + 1) + ", ";
log += "剩余瓶盖：" + (cap + 1) + ", ";
log += "已喝啤酒：" + (drinked + 1);
linkedList.addLast(log);
bottle = bottle - bottleCanChange + 1;
cap++;
drinked++;
} else if (cap >= capCanChange) {
String log = "";
log += "动作：瓶盖换酒, ";
log += "剩余金钱： " + (money) + ", ";
log += "剩余酒瓶：" + (bottle + 1) + ", ";
log += "剩余瓶盖：" + (cap - capCanChange + 1) + ", ";
log += "已喝啤酒：" + (drinked + 1);
linkedList.addLast(log);
bottle++;
cap = cap - capCanChange + 1;
drinked++;
} else {
break;
}
}
}
}
使用同一个Main函数运行即可，运行结果如下：
动作：买入啤酒, 剩余金钱： 8, 剩余酒瓶：1, 剩余瓶盖：1, 已喝啤酒：1;
动作：买入啤酒, 剩余金钱： 6, 剩余酒瓶：2, 剩余瓶盖：2, 已喝啤酒：2;
动作：买入啤酒, 剩余金钱： 4, 剩余酒瓶：3, 剩余瓶盖：3, 已喝啤酒：3;
动作：买入啤酒, 剩余金钱： 2, 剩余酒瓶：4, 剩余瓶盖：4, 已喝啤酒：4;
动作：买入啤酒, 剩余金钱： 0, 剩余酒瓶：5, 剩余瓶盖：5, 已喝啤酒：5;
动作：酒瓶换酒, 剩余金钱： 0, 剩余酒瓶：4, 剩余瓶盖：6, 已喝啤酒：6;
动作：酒瓶换酒, 剩余金钱： 0, 剩余酒瓶：3, 剩余瓶盖：7, 已喝啤酒：7;
动作：酒瓶换酒, 剩余金钱： 0, 剩余酒瓶：2, 剩余瓶盖：8, 已喝啤酒：8;
动作：酒瓶换酒, 剩余金钱： 0, 剩余酒瓶：1, 剩余瓶盖：9, 已喝啤酒：9;
动作：瓶盖换酒, 剩余金钱： 0, 剩余酒瓶：2, 剩余瓶盖：6, 已喝啤酒：10;
动作：酒瓶换酒, 剩余金钱： 0, 剩余酒瓶：1, 剩余瓶盖：7, 已喝啤酒：11;
动作：瓶盖换酒, 剩余金钱： 0, 剩余酒瓶：2, 剩余瓶盖：4, 已喝啤酒：12;
动作：酒瓶换酒, 剩余金钱： 0, 剩余酒瓶：1, 剩余瓶盖：5, 已喝啤酒：13;
动作：瓶盖换酒, 剩余金钱： 0, 剩余酒瓶：2, 剩余瓶盖：2, 已喝啤酒：14;
动作：酒瓶换酒, 剩余金钱： 0, 剩余酒瓶：1, 剩余瓶盖：3, 已喝啤酒：15
15
可以看出，其实两个方法的输出结果是一样的，但第二种方法和第一种比，省去了很多不必要的计算步骤。
如果不需要显示步骤，那么稍微归纳一下几次不同输入的结果（当然你也可以选择自己证明一下），可以总结出一个公式：
设你有n块钱，n>=4时，你可以喝的啤酒数为：2n-5（n为偶数时），2n-7（n为奇数时）
使用这个公式，应该是解决本题最快的方式了。
END