新英体育网直播曼城:分配问题---将八斤酒分成二等分的算法

波松分酒问题 C++求最优解.
　　/*
　　请设计程序解决“波松分酒问题”
　　问题如下：

　　某人有12品脱啤酒一瓶，想从中倒出6品脱，但他没有6品脱的容器，
　　仅有一个8品脱和一个5品脱的容器，怎样才能将啤酒分为两个6品脱？

　　抽象分析:

　　b = 大容器,也表示容积
　　s = 小容器,也表示容积
　　(f),(h),(e) 状态f=满, e=空, h=数字,表示容量

　　运算一: b(f) - s(e) => b(b - s), s(f)
　　变例 b(h) - s(e) => b(h - s), s(f)

　　运算二: b(e) + s(f) => b(s), s(e)
　　变例 b(h) + s(f) => b(f), s(s - b + h)

　　引出 b(f) - s(h)
　　b(h) - s(h)

　　b(e) + s(h)
　　b(h) + s(h)

　　如果以瓶中酒的数量为节点, 通过一次以上运算可达到节点之间认为连通.
　　此题可转化为一个有向图的搜索问题.
　　即找出.指定节点(12, 0, 0) 和 (6, 6, 0)之间的最小路径.

　　*/
　　#include <cstdio>
　　#include <deque>
　　#include <map>
　　#include <utility>
　　#include <queue>

　　static int big_max_value[] =
　　{
　　12, 8, 12
　　};
　　static int small_max_value[] =
　　{
　　8, 5, 5
　　};
　　static const int big_offset[] =
　　{
　　0, 1, 0
　　};
　　static const int small_offset[] =
　　{
　　1, 2, 2
　　};

　　//节点定义
　　class Node
　　{
　　unsigned char mBig;
　　unsigned char mMid;
　　unsigned char mSmall;

　　public:
　　static void InitMaxValue(int max1, int max2, int max3)
　　{
　　big_max_value[0] = max1;
　　big_max_value[1] = max2;
　　big_max_value[2] = max1;

　　small_max_value[0] = max2;
　　small_max_value[1] = max3;
　　small_max_value[2] = max3;
　　}

　　Node() : mBig(0), mMid(0), mSmall(0)
　　{
　　}

　　Node(unsigned char a, unsigned char b, unsigned char c) : mBig(a), mMid(b), mSmall(c)
　　{
　　}

　　enum OPCODE
　　{
　　BIG_OP_MIDDLE = 0,
　　MIDDLE_OP_SMALL,
　　BIG_OP_SMALL,
　　OP_LAST
　　};

　　//减运算
　　void sub(OPCODE op)
　　{
　　int big_max = big_max_value[op];
　　int small_max = small_max_value[op];

　　char& big = *(reinterpret_cast<char*>(this) + big_offset[op]);
　　char& small = *(reinterpret_cast<char*>(this) + small_offset[op]);

　　if (big > (small_max - small))
　　{
　　big -= (small_max - small);
　　small = small_max;
　　}
　　else
　　{
　　small += big;
　　big = 0;
　　}
　　}

　　//加运算
　　void add(OPCODE op)
　　{
　　int big_max = big_max_value[op];
　　int small_max = small_max_value[op];

　　char& big = *(reinterpret_cast<char*>(this) + big_offset[op]);
　　char& small = *(reinterpret_cast<char*>(this) + small_offset[op]);

　　if (small > big_max - big)
　　{
　　small -= big_max - big;
　　big = big_max;
　　}
　　else
　　{
　　big += small;
　　small = 0;
　　}
　　}

　　bool check(int value)
　　{
　　if (mBig == value || mMid == value || mSmall == value)
　　{
　　return true;
　　}
　　return false;
　　}

　　void print() const
　　{
　　printf("status [%d]=%2d, [%d]=%2d, [%d]=%2dn", big_max_value[0], mBig, big_max_value[1], mMid,
　　small_max_value[2], mSmall);
　　}

　　//相等性判定
　　friend bool operator==(Node const & a, Node const & b)
　　{
　　return memcmp(&a, &b, sizeof(Node)) == 0;
　　}

　　friend bool operator <(Node const & a, Node const & b)
　　{
　　return memcmp(&a, &b, sizeof(Node)) < 0;
　　}
　　};

　　template <class T>
　　void Search(T start, int value)
　　{
　　typedef std::pair<T, T> NodeValueType;

　　typedef std::map<T, T> NodeSet;
　　typedef NodeSet::iterator NodeSetIter;

　　typedef std::queue<NodeValueType, std::deque<NodeValueType> > NodeQueue;

　　NodeSet visited;
　　NodeQueue searchQueue;
　　NodeValueType last;

　　searchQueue.push(std::make_pair(start, start));

　　while (!searchQueue.empty())
　　{
　　NodeValueType cur = searchQueue.front();
　　searchQueue.pop();

　　visited.insert(cur);
　　if (cur.first.check(value))
　　{
　　last = cur;
　　break;
　　}

　　for (int i = 0; i < Node::OP_LAST; i++)
　　{
　　Node next1 = cur.first;
　　next1.sub(static_cast<Node::OPCODE>(i));

　　if (visited.find(next1) == visited.end())
　　{
　　searchQueue.push(std::make_pair(next1, cur.first));
　　}

　　Node next2 = cur.first;
　　next2.add(static_cast<Node::OPCODE>(i));

　　if (visited.find(next2) == visited.end())
　　{
　　searchQueue.push(std::make_pair(next2, cur.first));
　　}
　　}
　　}

　　NodeSetIter cur = visited.find(last.first);

　　while (!(cur->first == start))
　　{
　　cur->first.print();
　　cur = visited.find(cur->second);
　　}
　　cur->first.print();
　　}

　　int main()
　　{
　　puts("某人有12品脱啤酒一瓶，想从中倒出6品脱，但他没有6品脱的容器，n"
　　"仅有一个8品脱和一个5品脱的容器，怎样才能将啤酒分为两个6品脱？n");

　　for (int i = 0; i < 12; i++)
　　{
　　printf("---查找取得%d品脱的最少步骤,逆序------------n", i);
　　Search(Node(12, 0, 0), i);
　　}

　　puts("再解一个由13品脱啤酒，却一个9品脱和一个5品脱的容器n");

　　Node::InitMaxValue(13, 9, 5);
　　for (int i = 0; i < 12; i++)
　　{
　　printf("---查找取得%d品脱的最少步骤,逆序------------n", i);
　　Search(Node(13, 0, 0), i);
　　}
　　return 0;
　　}

　　实际上的最后一步,结果应是(6,6,0)但事实上我只做到出现一个6的情况.原因是并非所有结果都有两个相同的值.以下是我做出来的12,8,5的最优解法:
　　某人有12品脱啤酒一瓶，想从中倒出6品脱，但他没有6品脱的容器，
　　仅有一个8品脱和一个5品脱的容器，怎样才能将啤酒分为两个6品脱？

　　---查找取得0品脱的最少步骤,逆序------------
　　status [12]=12, [8]= 0, [5]= 0
　　---查找取得1品脱的最少步骤,逆序------------
　　status [12]= 1, [8]= 8, [5]= 3
　　status [12]= 9, [8]= 0, [5]= 3
　　status [12]= 9, [8]= 3, [5]= 0
　　status [12]= 4, [8]= 3, [5]= 5
　　status [12]= 4, [8]= 8, [5]= 0
　　status [12]=12, [8]= 0, [5]= 0
　　---查找取得2品脱的最少步骤,逆序------------
　　status [12]= 2, [8]= 5, [5]= 5
　　status [12]= 7, [8]= 5, [5]= 0
　　status [12]= 7, [8]= 0, [5]= 5
　　status [12]=12, [8]= 0, [5]= 0
　　---查找取得3品脱的最少步骤,逆序------------
　　status [12]= 4, [8]= 3, [5]= 5
　　status [12]= 4, [8]= 8, [5]= 0
　　status [12]=12, [8]= 0, [5]= 0
　　---查找取得4品脱的最少步骤,逆序------------
　　status [12]= 4, [8]= 8, [5]= 0
　　status [12]=12, [8]= 0, [5]= 0
　　---查找取得5品脱的最少步骤,逆序------------
　　status [12]= 7, [8]= 0, [5]= 5
　　status [12]=12, [8]= 0, [5]= 0
　　---查找取得6品脱的最少步骤,逆序------------
　　status [12]= 1, [8]= 6, [5]= 5
　　status [12]= 1, [8]= 8, [5]= 3
　　status [12]= 9, [8]= 0, [5]= 3
　　status [12]= 9, [8]= 3, [5]= 0
　　status [12]= 4, [8]= 3, [5]= 5
　　status [12]= 4, [8]= 8, [5]= 0
　　status [12]=12, [8]= 0, [5]= 0
　　---查找取得7品脱的最少步骤,逆序------------
　　status [12]= 7, [8]= 0, [5]= 5
　　status [12]=12, [8]= 0, [5]= 0
　　---查找取得8品脱的最少步骤,逆序------------
　　status [12]= 4, [8]= 8, [5]= 0
　　status [12]=12, [8]= 0, [5]= 0
　　---查找取得9品脱的最少步骤,逆序------------
　　status [12]= 9, [8]= 3, [5]= 0
　　status [12]= 4, [8]= 3, [5]= 5
　　status [12]= 4, [8]= 8, [5]= 0
　　status [12]=12, [8]= 0, [5]= 0
　　---查找取得10品脱的最少步骤,逆序------------
　　status [12]=10, [8]= 2, [5]= 0
　　status [12]= 5, [8]= 2, [5]= 5
　　status [12]= 5, [8]= 7, [5]= 0
　　status [12]= 0, [8]= 7, [5]= 5
　　status [12]= 7, [8]= 0, [5]= 5
　　status [12]=12, [8]= 0, [5]= 0
　　---查找取得11品脱的最少步骤,逆序------------
　　status [12]=11, [8]= 0, [5]= 1
　　status [12]= 3, [8]= 8, [5]= 1
　　status [12]= 3, [8]= 4, [5]= 5
　　status [12]= 8, [8]= 4, [5]= 0
　　status [12]= 8, [8]= 0, [5]= 4
　　status [12]= 0, [8]= 8, [5]= 4
　　status [12]= 4, [8]= 8, [5]= 0
　　status [12]=12, [8]= 0, [5]= 0
　　注意这个解法通用性很强,还可以解其它的组合:如最后的13,9,5.

十斤坛子=a, 七斤坛子=b,三斤坛子=c

(1) a倒酒去c

(2) c倒酒去b

(3) a倒酒去c

(4) c倒酒去b

(5) a倒酒去c

现在是 a有一斤酒, b有六斤酒, c有三斤酒

(6) c倒一斤酒去b

变了a有一斤酒, b有七斤酒, c有二斤酒

(7)b倒酒去a

a有八斤酒, b无酒, c有二斤酒

(8) c倒酒去a

a有八斤酒, b有二斤酒, c无酒

(9) a倒酒去c

a有五斤酒, b有二斤酒, c有三斤酒

(10) c倒酒去b

a有五斤酒, b有五斤酒, c无酒

楼上的 人家是8斤 随便搜个答案发出来
不负责任
我可是当场算的

3/8 5/5 0/3
3/8 2/5 3/3
6/8 2/5 0/3
6/8 0/5 2/3
1/8 5/5 2/3
1/8 4/5 3/3
4/8 4/5 0/3
OK 解决了 希望看的懂 说起来太麻烦了 现场解决
给点奖励^_^

不错，楼上的回答完全可以