广泛版的倒水问题如何实现
倒水问题:有几个容量不全相等的杯子，一部分杯子里有一定量的水，要求通过有限次倒水使各杯子里的水达到一定量。
倒水规则:
每次倒水都要把本杯子的水倒完或者把被倒杯子倒满。
要求：
输入 杯子个数，容量，初始水量和末水量。//例如杯子数4，容量21 11 8 5，出事水量21 0 0 0，末水量7 7 7 0
输出 倒水步骤或者无解。
这个问题困扰我好几天了，一直没有想到解决方法，在百度贴吧还有各种c++交流群里都问了，新手不会，大神不理
程序代码：void pour( size_t size, const unsigned volume[], const unsigned initial[], const unsigned terminate[] );
int main( void )
{
// 杯子数4，容量分别为21,11,8,5，初始水量分别为21,0,0,0，末水量7,7,7,0
const unsigned volume[4] = { 21, 11, 8, 5 };
const unsigned initial[4] = { 21, 0, 0, 0 };
const unsigned terminate[4] = { 7, 7, 7, 0 };
pour( 4, volume, initial, terminate );
return 0;
}
#include <iostream>
#include <vector>
void pour( size_t size, const unsigned volume[], const unsigned initial[], const unsigned terminate[] )
{
struct foo
{
size_t parent;
size_t from;
size_t to;
std::vector<unsigned> yield;
};
std::vector<foo> a( 1 );
a[0].parent = 0;
a[0].from = 0;
a[0].to = 0;
a[0].yield = std::vector<unsigned>( initial+0, initial+size );
const std::vector<unsigned> b( terminate+0, terminate+size );
for( size_t i=0; i!=a.size(); ++i )
{
if( a[i].yield == b )
{
std::vector<foo*> ret;
for( size_t j=i; j!=0; j=a[j].parent )
ret.push_back( &a[j] );
std::cout << "Volu: ";
for( size_t j=0; j!=size; ++j )
std::cout << '\t' << volume[j];
std::cout << '\n';
std::cout << "Init: ";
for( size_t j=0; j!=size; ++j )
std::cout << '\t' << initial[j];
std::cout << '\n';
for( std::vector<foo*>::const_reverse_iterator itor=ret.rbegin(); itor!=ret.rend(); ++itor )
{
const foo& f = **itor;
std::cout << char('A'+f.from) << "->" << char('A'+f.to) << ": ";
for( size_t k=0; k!=f.yield.size(); ++k )
std::cout << '\t' << f.yield[k];
std::cout << '\n';
}
return;
}
for( size_t j=0; j!=a[i].yield.size(); ++j )
{
for( size_t k=0; k!=a[i].yield.size(); ++k )
{
if( j!=k && a[i].yield[j]!=0 && a[i].yield[k]!=volume[k] )
{
std::vector<unsigned> cur = a[i].yield;
if( cur[j]+cur[k] <= volume[k] )
{
cur[k] += cur[j];
cur[j] = 0;
}
else
{
cur[j] -= volume[k]-cur[k];
cur[k] = volume[k];
}
bool bfound = false;
for( size_t m=0; !bfound && m!=a.size(); ++m )
if( a[m].yield == cur )
bfound = true;
if( !bfound )
{
a.push_back( foo() );
a.back().parent = i;
a.back().from = j;
a.back().to = k;
a.back().yield.swap( cur );
}
}
}
}
}
return;
}输出：
Volu: 21 11 8 5
Init: 21 0 0 0
A->B: 10 11 0 0
B->D: 10 6 0 5
B->C: 10 0 6 5
D->A: 15 0 6 0
C->D: 15 0 1 5
D->B: 15 5 1 0
C->D: 15 5 0 1
A->C: 7 5 8 1
C->B: 7 11 2 1
B->D: 7 7 2 5
D->C: 7 7 7 0
Init: 21 0 0 0
A->B: 10 11 0 0
B->D: 10 6 0 5
B->C: 10 0 6 5
D->A: 15 0 6 0
C->D: 15 0 1 5
D->B: 15 5 1 0
C->D: 15 5 0 1
A->C: 7 5 8 1
C->B: 7 11 2 1
B->D: 7 7 2 5
D->C: 7 7 7 0
[此贴子已经被作者于2016-5-4 14:14编辑过]