Mother’s Milk
Farmer John has three milking buckets of capacity A, B, and C liters. Each of the numbers A, B, and C is an integer from 1 through 20, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out.
Write a program to help FJ determine what amounts of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty.
PROGRAM NAME: milk3
INPUT FORMAT
A single line with the three integers A, B, and C.
SAMPLE INPUT (file milk3.in)
8 9 10
OUTPUT FORMAT
A single line with a sorted list of all the possible amounts of milk that can be in bucket C when bucket A is empty.
SAMPLE OUTPUT (file milk3.out)
1 2 8 9 10
SAMPLE INPUT (file milk3.in)
2 5 10
SAMPLE OUTPUT (file milk3.out)
5 6 7 8 9 10
个人深搜解：这样编程需要很认真，否则容易出错，我也是调了挺久的
/*
ID:nealgav1
PROG:milk3
LANG:C++
*/
#include
#include
using namespace std;
int a,b,c;
bool s[22][22][22];
bool flag[23];
void dfs(int aa,int bb,int cc)
{
if(s[aa][bb][cc])return;
s[aa][bb][cc]=1;
int x;
if(aa==0)
{
flag[cc]=1;
if(aa+cca
else {x=a-aa;cc-=x;aa+=x;dfs(aa,bb,cc);cc+=x;aa-=x;}
if(aa+bba
else {x=a-aa;bb-=x;aa+=x;dfs(aa,bb,cc);bb+=x;aa-=x;}
if(bb+ccc
else{x=(c-cc);cc+=x;bb-=x;dfs(aa,bb,cc);bb+=x;cc-=x;}
if(bb+ccb
else{x=(b-bb);bb+=x;cc-=x;dfs(aa,bb,cc);bb-=x;cc+=x;}
}
else
{
if(aa+bbb
else{x=(b-bb);aa-=x;bb+=x;dfs(aa,bb,cc);bb-=x;aa+=x;}
if(aa+ccc
else{x=(c-cc);aa-=x;cc+=x;dfs(aa,bb,cc);cc-=x;aa+=x;}
if(aa+cca
else {x=a-aa;cc-=x;aa+=x;dfs(aa,bb,cc);cc+=x;aa-=x;}
if(aa+bba
else {x=a-aa;bb-=x;aa+=x;dfs(aa,bb,cc);bb+=x;aa-=x;}
if(bb+ccc
else{x=(c-cc);cc+=x;bb-=x;dfs(aa,bb,cc);bb+=x;cc-=x;}
if(bb+ccb
else{x=(b-bb);bb+=x;cc-=x;dfs(aa,bb,cc);bb-=x;cc+=x;}
}
}
int main()
{ int aa,bb,cc;
ifstream fin("milk3.in");
ofstream fout("milk3.out");
while(fin>>a>>b>>c)
{
memset(flag,0,sizeof(flag));
memset(s,0,sizeof(s));
dfs(0,0,c);
int ans=0;
for(int i=0;i
以下摘自独孤的博客，感觉着个方法代码敲的少，不易错
还是个搜索题，每次最多无非有6种倒法，即a->b;a->c;b->a;b->c;c->a;c->b。所以如果用a、b、c代表三个桶的容积，x、y、z代表当前三个桶内的牛奶数，那么不难算出执行完a->b后，x变为max(0,x+y-b)，y变为min(b,x+y)，z不变。其它倒法类似。
最后注意判重最好的方法就是用bool数组flag[i][j][k]表示a、b、c桶分别装i、j、k升牛奶这种状态是否曾经搜到过。但由于牛奶总数不变，故知道了i和j，其实k也就知道了，所以用二维bool数组flag[i][j]就够了。
源码如下：
|
USER: Neal Gavin Gavin [nealgav1]
TASK: milk3
LANG: C++
Compiling…
Compile: OK
Executing…
Test 1: TEST OK [0.011 secs, 3348 KB]
Test 2: TEST OK [0.000 secs, 3348 KB]
Test 3: TEST OK [0.000 secs, 3348 KB]
Test 4: TEST OK [0.000 secs, 3348 KB]
Test 5: TEST OK [0.000 secs, 3348 KB]
Test 6: TEST OK [0.000 secs, 3348 KB]
Test 7: TEST OK [0.000 secs, 3348 KB]
Test 8: TEST OK [0.000 secs, 3348 KB]
Test 9: TEST OK [0.000 secs, 3348 KB]
Test 10: TEST OK [0.000 secs, 3348 KB]
All tests OK.
Your program (‘milk3’) produced all correct answers! This is your
submission #2 for this problem. Congratulations!
Here are the test data inputs:
------- test 1 ----
2 5 10
------- test 2 ----
20 20 20
------- test 3 ----
5 11 15
------- test 4 ----
2 12 20
------- test 5 ----
19 4 11
------- test 6 ----
5 11 13
------- test 7 ----
3 20 20
------- test 8 ----
7 16 20
------- test 9 ----
20 10 9
------- test 10 ----
7 12 18
Keep up the good work!
Mother’s Milk
Russ Cox
We use a simple depth-first search to find all the possible states for the three buckets, pruning the search by not researching from states we’ve seen before.
#include
#include
#include
#include
#include
#define MAX 20
typedef struct State State;
struct State {
int a[3];
};
int seen[MAX+1][MAX+1][MAX+1];
int canget[MAX+1];
State
state(int a, int b, int c)
{
State s;
s.a[0] = a;
s.a[1] = b;
s.a[2] = c;
return s;
}
int cap[3];
/* pour from bucket "from" to bucket "to" */
State
pour(State s, int from, int to)
{
int amt;
amt = s.a[from];
if(s.a[to]+amt > cap[to])
amt = cap[to] - s.a[to];
s.a[from] -= amt;
s.a[to] += amt;
return s;
}
void
search(State s)
{
int i, j;
if(seen[s.a[0]][s.a[1]][s.a[2]])
return;
seen[s.a[0]][s.a[1]][s.a[2]] = 1;
if(s.a[0] == 0) /* bucket A empty */
canget[s.a[2]] = 1;
for(i=0; iRan Pang from Canada sends this non-recursive DP solution:
#include
int m[21][21][21];
int poss[21];
int A, B, C;
int main(void) {
int i,j,k;
int flag;
FILE* in=fopen("milk3.in","r");
fscanf(in, "%d %d %d",&A, &B, &C);
fclose(in);
for(i=0;i=i) {
if( m[0][j+i][k]==0) {
m[0][j+i][k]=1;
flag=1;
}
} else {
if( m[i-(B-j)][B][k] == 0) {
m[i-(B-j)][B][k] =1;
flag=1;
}
}
}
if(k=i) {
if( m[0][j][k+i]==0) {
m[0][j][k+i]=1;
flag=1;
}
}
else {
if( m[i-(C-k)][j][C] == 0) {
m[i-(C-k)][j][C] =1;
flag=1;
}
}
}
}
if(j) {
if(i=j) {
if( m[i+j][0][k]==0) {
m[i+j][0][k]=1;
flag=1;
}
} else {
if( m[A][j-(A-i)][k] == 0) {
m[A][j-(A-i)][k] =1;
flag=1;
}
}
}
if(k=j) {
if( m[i][0][k+j]==0) {
m[i][0][k+j]=1;
flag=1;
}
} else {
if( m[i][j-(C-k)][C] == 0) {
m[i][j-(C-k)][C] =1;
flag=1;
}
}
}
}
if(k) {
if(i=k) {
if( m[i+k][j][0]==0) {
m[i+k][j][0]=1;
flag=1;
}
} else {
if( m[A][j][k-(A-i)] == 0) {
m[A][j][k-(A-i)] =1;
flag=1;
}
}
}
if(j=k) {
if( m[i][j+k][0]==0) {
m[i][j+k][0]=1;
flag=1;
}
} else {
if( m[i][B][k-(B-j)] == 0) {
m[i][B][k-(B-j)] =1;
flag=1;
}
}
}
}
}
}
}
{
FILE* out=fopen("milk3.out", "w");
for(i=0;iDaniel Jasper from Germany writes:
Both other solutions (recursive and non-recursive) use a 3D-array to store the states, so that the memory usage is O(N3). However a 2D Array and O(N2) would be enough since a state is uniquely defined by the amount of milk in bucket B and C. The amount of milk in bucket A is size-of-C minus amount-in-C minus amount-in-B. This solution works with it, and is a little bit shorter (though not more elegant):
#include
int A, B, C;
int CB[21][21]; // All states
void readFile() {
FILE *f;
f = fopen("milk3.in", "r");
fscanf(f, "%d%d%d", &A, &B, &C);
fclose(f);
}
void writeFile() {
FILE *f; int i;
f = fopen("milk3.out", "w");
for(i = 0; i b
if(B c
if(C a
if(A c
if(C a
if(A b
if(B
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
在过去的数年里，我们见证了机器学习和计算机科学领域的很多变化。人工智能应用也愈趋广泛，正在加速融入人们的日常生活之中。机器学习作为技术核心，也在持续地发展进化，在更多领域发挥出越来越重要的作用。机器学习会有哪些新的演进趋势和发展方向？我们又该如何提前布局，紧跟…
