|
|
> No.3616[元記事へ]
問題 几帳MEN
30個のみかんがあります。
3人で10個ずつ分けようと思いますが、不公平にならないように、
みかんの重さの合計が均一になるように分けてください。
考察
まず、
問題
9個のみかんがあります。
3人で3個ずつ分けようと思いますが、不公平にならないように、
みかんの重さの合計が均一になるように分けてください。
の場合、
組み合わせで考えると、C(9,3)、C(6,3)と選んでいく。
DATA 9 !個数
DATA 86,106,85,128,95,96,91,102,108 !重さ
READ N
DIM B(N)
MAT READ B
LET S=0
FOR i=1 TO N
LET S=S+B(i)
NEXT i
PRINT S; S/3 !合計
DIM F(N) !選択されたかどうか
MAT F=ZER
FOR P=1 TO N-2 !1つ目を選ぶ（組み合わせの基準とする）
IF F(P)=0 THEN
LET X=P+1 !2つ目を選ぶ
DO WHILE X<=N-1
IF F(X)=0 THEN
FOR Y=X+1 TO N !3つ目を選ぶ
IF F(Y)=0 THEN
IF B(P)+B(X)+B(Y)=S/3 THEN !題意を満たす
LET F(X)=1
LET F(Y)=1
PRINT B(P);B(X);B(Y)
!!!EXIT DO !解の1つ
END IF
END IF
NEXT Y
END IF
LET X=X+1
LOOP
END IF
NEXT P
END
実行結果
897 299
86 85 128
106 91 102
95 96 108
30個なら、C(30,10)、C(20,10)となって、検索範囲が増大する。
そこで、
ほぼ均等に分けると、それぞれ1回程度の交換で完成させることが期待できる。これを使って、1つの解を得る。
（終わり）
答え
85,86,91,95,96,102,106,108,128と昇順に並べる。
次のように、ほぼ均等に分ける。
A: 1番目 6番目 7番目
B: 2番目 5番目 8番目
C: 3番目 4番目 9番目
すなわち、
A: 85,102,106 =293
B: 86, 96,108 =290
C: 91, 95,128 =314
Aから順に、揃えていく。
・Aの85を移動させることを考える。299-293=6なので、85+6=91
A: (91), 102 , 106 =299
B: 86 , 96 , 108 =290
C: (85), 95 , 128 =308
続いて、Bの86を移動させることを考える。299-290=9なので、86+9=95
A: 91 , 102 , 106 =299
B: (95), 96 , 108 =299
C: 85 , (86), 128 =299
続いて、Bの96,108を移動させることを考える。105,117になるので、移動できるものがない。
・Aの102を移動させることを考える。299-293=6なので、102+6=108
A: 85 , (108), 106 =299
B: 86 , 96 , (102) =284
C: 91 , 95 , 128 =314
続いて、Bの86,96,102を移動させることを考えるが、これらは移動できない。
A: 85 , 108 , 106 =299
B: 86 , 96 , 102 =284
C: 91 , 95 , 128 =314
・Aの106を移動させることを考える。
299-293=6なので、106+6=112になるので、移動できるものがない。
（終わり）
DATA 9 !個数
DATA 86,106,85,128,95,96,91,102,108 !重み
!DATA 30 !個数
!DATA 138,104,139,124,157,128,134,150,157, 81 !重み
!DATA 159,159, 98,134,147,154,113,117,138,156
!DATA 116,147, 81,150, 95,131,156, 91,105,132
READ N
DIM D(N)
MAT READ D
LET S=0
FOR i=1 TO N
LET S=S+D(i)
NEXT i
PRINT S; S/3
FOR i=1 TO N-1 !並べ替える
FOR J=i+1 TO N
IF D(i)>D(J) THEN
LET T=D(i) !swap it
LET D(i)=D(J)
LET D(J)=T
END IF
NEXT J
NEXT i
MAT PRINT D;
DATA 3 !ほぼ均等に分ける
DATA 1,6,7
DATA 2,5,8
DATA 3,4,9
!DATA 10 !ほぼ均等に分ける
!DATA 1,6,7,12,13,18,19,24,25, 28
!DATA 2,5,8,11,14,17,20,23,26, 29
!DATA 3,4,9,10,15,16,21,22,27, 30
READ K
DIM A(N)
FOR i=1 TO N
READ T
LET A(i)=D(T)
NEXT i
MAT PRINT USING REPEAT$(" ###",K): A
FOR P=1 TO N/K
LET T=0 !p番目の人の合計
FOR i=1 TO K
LET T=T+A((P-1)*K+i)
NEXT i
PRINT T
NEXT P
PRINT
CALL try(1,N,A,K,S/3) !移動を試みる
END
EXTERNAL SUB try(P,N,A(),K,S) !1つ移動させる
LET T=0 !p番目の人の合計
FOR i=1 TO K
LET T=T+A((P-1)*K+i)
NEXT i
PRINT T !debug
IF P=N/K THEN !最後の人なら
MAT PRINT USING REPEAT$(" ###",K): A
ELSE
FOR i=1 TO K !p番目の人のi番目のみかんを入れ替える
LET X=(P-1)*K+i
FOR J=P*K+1 TO N !(p+1)番目以降の人のみかんが対象である
IF T-A(X)+A(J)=S THEN !可能なら
PRINT P; X;J !debug
LET W=A(X) !swap it
LET A(X)=A(J)
LET A(J)=W
CALL try(P+1,N,A,K,S) !次の人へ
LET W=A(X) !元に戻す
LET A(X)=A(J)
LET A(J)=W
END IF
NEXT J
NEXT i
END IF
END SUB
実行結果
897 299
85 86 91 95 96 102 106 108 128
85 102 106
86 96 108
91 95 128
293
290
314
293
1 1 7
290
2 4 8
299
91 102 106
95 96 108
85 86 128
1 2 6
284
|
|