[ 初めての方へ | 一覧(最新更新順) | 全文検索 | 過去ログ ]
『組み合わせの問題』（ナップサック）
以下のような組み合わせを自動で行いたいと考えています。
ある数字の中から３個使用して
１０以上１２以下
同じ数字を使わずに
選んだ数字の最小値と最大値の差が６以下であり
できるだけ多くの組み合わせを表示したい。
例えば
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5
という中から 1 2 8 3 4 5 4 5 2 7 1 3 のような組み合わせが１１になりますが 1 2 8は最小値と最大値が離れているからNGとなる。
このような関数なりVBAの組み方をご教示いただければと思います。
＜ 使用 Excel：Microsoft365、使用 OS：unknown ＞
まずは、日本語で「組み方」を考えるのは、ご自身だと思います。
その上で、VBAのコードの書き方が分からないなら質問する方が良いかと…
＞ 1 2 8
＞ 3 4 5
＞ 4 5 2
＞ 7 1 3
＞ のような組み合わせが１１になりますが
１１というのは、11通りという事でしょうか、
それとも全角文字の「１１」でしょうか？
＞1 2 8は最小値と最大値が離れているからNGとなる。
NGというのは、「NG」と出力(表示)するのでしょうか？
それとも、再度数字を選びなおすという事でしょうか？
VBAなら
・Rnd
・Array
・If
について調べてみて下さい
（匿名） 2024/03/28(木) 09:31:03
3文字を組み合わせる際の条件は以下ですね。 (A)3数値の差が6以下 (B)3数値の和が10以上12以下
(1) 上の(条件A),(条件B)を組み合わせると、10,9,8 は使用できないことがわかります。 また、3文字がすべて3以下の場合も不可です。 そこで、 ・7を使用する場合の採り得る組み合わせ ・6を使用する場合の採り得る組み合わせ ・・・ ・4を使用する場合の採り得る組み合わせ を限定列挙しておきます。 (2) それらのパターンを二つ組み合わせたときに、 1から5までは2回使用可。6以降は一回だけという 使用可能回数条件により、これに抵触するものを排除します。
(3) さらに、これにもうひとつのパターンを組み合わせた場合のパターンを調べて、 使用可能回数によるチェックを行います。
こんな感じで、やればできると思われます。
実際にどんなことに使用されるのかを書かれないと、取組む気にはなれません。 お察しください。
（xyz） 2024/03/28(木) 09:34:19
xyzさま
こういった分けて考えることが苦手なため、とても参考になりました。
実際の数字はランダムで桁数も多く同一の数字はほぽ無いのですが、
簡略化しないと自分で組み合わせ説明できなかったためこのような質問の仕方になってしまいました。
実際には製品の重量を組み合わせて、合計がその範囲に入るような組み合わせをできるだけ多く作る、といったことに使用したいと考えています。
仕様により重量範囲は毎回違うのですが
56.53g
54.22g
49.55g
・
・
・
のような製品(仕掛品)が100個以上あり、
そこで三個の合計が160〜170g内で
最小重量と最大重量の差が6g以内のよう
できるだけ多く(廃棄で製品が無駄にならないよう)
組み合わせるということを人力で行っています。
お二人ともありがとうございました。
組み立て方から考えて、また質問できたらと思います。
（ナップサック） 2024/03/28(木) 11:22:00
入力:
次の数字の中から同じ数字を使わず3個を抽出しその合計が10以上12以下、選んだ数字の最小値と最大値の差が６以下となる組み合わせを全部表示して 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5
回答 :
数字の中から同じ数字を使わず3つを抽出し、その合計が10以上12以下であり、選んだ数字の最小値と最大値の差が6以下となる組み合わせを見つけましょう。
1, 2, 7 (合計: 10, 差: 6)
1, 3, 6 (合計: 10, 差: 5)
1, 4, 5 (合計: 10, 差: 4)
2, 3, 5 (合計: 10, 差: 3)
2, 4, 6 (合計: 12, 差: 4)
3, 4, 5 (合計: 12, 差: 2)
これらの組み合わせは、条件を満たす数字の選択肢です。1
（abec） 2024/03/28(木) 12:11:18
具体的な数値が出たので 100個の製品から3つ選ぶ組合せは「100C3=161,700通り」なので、その程度であれば何とかなりそうです。
VBAか、365ならPower Queryでも可能と思います。 中身はわからなくても、答えだけでいいなら考えてみますけど....
（まる2021） 2024/03/28(木) 12:41:20
> のような製品(仕掛品)が100個以上あり、 > そこで三個の合計が160〜170g内で > 最小重量と最大重量の差が6g以内のよう > できるだけ多く(廃棄で製品が無駄にならないよう) > 組み合わせるということを人力で行っています。
これは単純に100個の中から条件にあう3つを選ぶだけということではなく、 100個の中から条件にあう3つの組み合わせを、なるべく多く(廃棄分が少なく)なるように 選ぶという問題ですかね。
想定される組み合わせの最大数は33個(廃棄1製品)ということになりますね。
だとするとナップサック問題のバリエーションということになりそうです。 偶然にもユザネと同じですね（わかって付けたのかな）
https://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C
Wikipediaによると解法としては、動的計画法とかいろいろあるそうですが、私にはちょっと荷が重いので 他の方の回答をお待ちください。 （hatena） 2024/03/28(木) 13:32:08
質問者さんへ。 こうした話は、量は質に転化するといいますか、まったく別の問題と言っていいでしょう。 単純化しすぎると問題の本質が変わってしまいます。質問の際は気をつけてください。
確認ですが、当初の質問では、 | できるだけ多くの組み合わせを表示したい。 とのことでした。 ある意味で、ケースの全列挙ですよね。
しかし、修正質問は何か最適化問題のような気もします。 | できるだけ多く(廃棄で製品が無駄にならないよう) | 組み合わせるということを人力で行っています。 何を最大化するのですか？ そこを明確にしてください。（次に発言するタイミングで結構です。）
abecさんへ。 Copilotですか、参考情報ありがとうございます。 それで、その回答は正しいと受け止めているのでしょうか。 例えば、合計が11になるものなど他のケースはないんですか？ それと、 | 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 のなかから取り出す、 という条件はどこに効いてきているんですか？ 私には、理解ができませんでした。
（xyz） 2024/03/28(木) 13:41:01
A B C D E F G 1 52.46 52.46 56.49 55.6 和164.55 差4.03 2 59.7 59.7 54.92 55.21 和169.83 差4.78 3 49.07 57.39 52.81 53.35 和163.55 差4.58 4 56.49 51.56 53.27 57.14 和161.97 差5.58 5 55.6 51.84 56.96 56.31 和165.11 差5.12 6 49.92 7 57.39 8 52.81 9 53.35 10 51.56 11 53.27 12 51.84 13 57.14 14 54.92 15 55.21 16 56.96 17 51.15 18 56.31 19 56.17 20 49.56
C1 =LET(a,A1:A100,Ct,3,Mn,160,Mx,170,Rg,6, b,FILTER(a,a<>""),c,SEQUENCE(COUNTA(b)), E,LAMBDA(x,y,DROP(REDUCE(0,c,LAMBDA(s,i, LET(j,FILTER(y,BYROW(y,LAMBDA(z,i<MIN(z)))), IFERROR(VSTACK(s,HSTACK(IF(SEQUENCE(ROWS(j)),i),j)),s)))),1)), k,REDUCE(c,SEQUENCE(Ct-1),LAMBDA(i,t,E(c,i))), d,HSTACK(k,BYROW(k,LAMBDA(i,LET(y,INDEX(b,i), (SUM(y)>=Mn)*(SUM(y)<=Mx)*(MAX(y)-MIN(y)<=Rg))))), Z,LAMBDA(x,y,FILTER(x,BYROW(x,LAMBDA(i, AND(ISNA(XMATCH(DROP(i,,-1),DROP(y,,-1)))))))), F,LAMBDA(F,x,v,LET(k,XMATCH(1,TAKE(x,,-1)),j,CHOOSEROWS(x,k), IF(ISERROR(k),v,F(F,Z(x,j),VSTACK(v,j))))), h,INDEX(b,DROP(DROP(F(F,d,""),1),,-1)), HSTACK(h,"和"&BYROW(h,SUM),"差"&BYROW(h,LAMBDA(i,MAX(i)-MIN(i))))) 結果はいい加減なものですので、あしからず。 （んなっと） 2024/03/28(木) 19:25:53
Sub main()
'１行目（A１セルから）に列方向に全重量データをセットして実施
'A３セル以下に結果表示します
Dim dt(), i As Long, c1 As Range, c2 As Range, c3 As Range
ReDim dt(Rows.Count, 2)
Application.ScreenUpdating = False
Rows("2:" & Rows.Count).ClearContents
For Each c In Rows(1).SpecialCells(2)
c.Offset(1).Formula = "=LARGE(1:1,COLUMN())"
Next c
Rows(2).Cells.Value = Rows(2).Cells.Value
For Each c In Rows(2).SpecialCells(2)
If WorksheetFunction.CountIf(Range(Cells(2, 1), c), c.Value) > 1 Then c.ClearContents
If c.Value >= 160 Then c.ClearContents
Next c
Rows(2).SpecialCells(xlCellTypeBlanks).Delete Shift:=xlToLeft
For Each c1 In Range(Range("A2"), Cells(2, Columns.Count).End(xlToLeft))
For Each c2 In Range(c1.Offset(, 1), Cells(2, Columns.Count).End(xlToLeft))
If c1.Value + c2.Value < 170 And Abs(c1.Value - c2.Value) <= 6 Then
For Each c3 In Range(c2.Offset(, 1), Cells(2, Columns.Count).End(xlToLeft))
If c1.Value <> "" And c2.Value <> "" And c3.Value <> "" And c1 <> c2 And c2 <> c3 Then
If c1.Value + c2.Value + c3.Value >= 160 And c1.Value + c2.Value + c3.Value <= 170 Then
If WorksheetFunction.Max(c1.Value, c2.Value, c3.Value) - WorksheetFunction.Min(c1.Value, c2.Value, c3.Value) <= 6 Then
dt(i, 0) = c1.Value: dt(i, 1) = c2.Value: dt(i, 2) = c3.Value
i = i + 1
End If
End If
End If
DoEvents
Next c3
End If
Next c2
Next c1
Range("A3").Resize(i, 3) = dt
Rows(2).ClearContents
End Sub
（mm） 2024/04/01(月) 15:59:05
和条件(例：160〜170の間）と差条件(最大と最小が6以下）を満たす3要素からなるセットを 列挙することは比較的容易です。 問題は、保有している各部品の種類と数の制限のなかで、 それらをできるだけ多く組み合わせるには、どうしたらよいか、と言う点です。
んなっとさんの計算では、条件を満たすセットをもとに、 それと３つの要素が重ならないように、次々にセットを選択していくわけですが、 これは最初にどのセットをとるかに依存します。
提示いただいた20個の例でも、初期セットを別のものに変えた場合、 4つの組み合わせしか得られないことも起こり得ます。 (提示いただいたケースでは６個のセットが得られないことは論理的に詰められますが、 100個になった場合は、最大のセットがいくつになるかは、そう簡単ではありません。）
さらに、現実的な個数（例：100個）に適用させる場合、どのようにすべきかという話になります。 ・本来は、綺麗なアルゴリズムで求められればそれに越したことはないのですが、 ・初期条件を色々変えてシミュレーションして、得られる最大のセット数を求めることが 現実的かと思います。（100個の場合でも、さほど計算負荷は大きくないように思います。） （理論上は、(a)初期条件だけでなく、(b)どのような順序でセットを当てて、 セットの数を増やしていくか、にも依存するかもしれません。 まあ、その辺は実務上の要請がどの程度の精度を求めているかによるでしょう。）
そうしたシミュレーション方式が妥当かと思っていますが、 そうではない何か気の利いたアルゴリズムをお持ちの方は、お知らせください。 （xyz） 2024/04/01(月) 21:39:09
再度手直し。
=LET(a,A1:A150,Ct,3,Mn,160,Mx,170,Rg,6, b,FILTER(a,a<>""),c,SEQUENCE(COUNTA(b)), E,LAMBDA(x,y,DROP(REDUCE(0,c,LAMBDA(s,i, LET(j,FILTER(y,BYROW(y,LAMBDA(z,i<MIN(z)))), IFERROR(VSTACK(s,HSTACK(IF(SEQUENCE(ROWS(j)),i),j)),s)))),1)), k,REDUCE(c,SEQUENCE(Ct-1),LAMBDA(i,t,E(c,i))), d,FILTER(k,BYROW(k,LAMBDA(i,LET(y,INDEX(b,i), (SUM(y)>=Mn)*(SUM(y)<=Mx)*(MAX(y)-MIN(y)<=Rg))))), W,LAMBDA(x,LET(i,IFERROR(TEXT(FREQUENCY(x,c),"0;;")*1,""),j,XMATCH(MIN(i),i), AGGREGATE(14,6,BYCOL(x,LAMBDA(y,XMATCH(j,y))),1))), Z,LAMBDA(x,y,FILTER(x,BYROW(x,LAMBDA(i, AND(ISNA(XMATCH(i,y))))))), F,LAMBDA(F,x,[v],LET(j,CHOOSEROWS(x,W(x)), IF(ISERROR(j),v,F(F,Z(x,j),IF(ISOMITTED(v),j,VSTACK(v,j)))))), m,F(F,SORT(d)),n,F(F,SORT(d,,-1)),l,IF(ROWS(m)>ROWS(n),m,n),h,INDEX(b,l), HSTACK(h,"和"&BYROW(h,SUM),"差"&BYROW(h,LAMBDA(i,MAX(i)-MIN(i)))))
（んなっと） 2024/04/02(火) 21:55:20
最初の質問の命題と、途中で出された要件では、 まったく次元が異なる話になっていますので、 仕様の確認をさせてください。
最初の質問では、「同じ数字を使わずに」という条件がありますが、 実際の仕様でもこの条件は必要ですか。 「実際の数字はランダムで桁数も多く同一の数字はほぽ無い」 とのことなのでなくてもいいと思いますがどうでしょう。
「(廃棄で製品が無駄にならないよう)」という点について、 廃棄数がなるべく少なくなるようにということでしょうか。 それとも、破棄する製品の重量計が最小になるようにということでしょうか。
あと、これは興味本位の質問ですが、 ナップサック というユーザーネームは、 「ナップサック問題」と言われている命題が存在することを知った上で つけたものですか。それとも偶然、一致したものでしょうか。
ナップサック問題 - Wikipedia https://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C （hatena） 2024/04/03(水) 10:46:54
しつこく変更。
=LET(a,A1:A150,Ct,3,Mn,160,Mx,170,Rg,6, b,FILTER(a,a<>""),c,SEQUENCE(COUNTA(b)), E,LAMBDA(x,y,DROP(REDUCE(0,c,LAMBDA(s,i, LET(j,FILTER(y,BYROW(y,LAMBDA(z,i<MIN(z)))), IFERROR(VSTACK(s,HSTACK(IF(SEQUENCE(ROWS(j)),i),j)),s)))),1)), k,REDUCE(c,SEQUENCE(Ct-1),LAMBDA(i,t,E(c,i))), d,FILTER(k,BYROW(k,LAMBDA(i,LET(y,INDEX(b,i), (SUM(y)>=Mn)*(SUM(y)<=Mx)*(MAX(y)-MIN(y)<=Rg))))), W,LAMBDA(x,LET(i,IFERROR(TEXT(FREQUENCY(x,c),"0;;")*1,""), p,BYROW(x,LAMBDA(s,SUM(INDEX(i,s)))),CHOOSEROWS(x,XMATCH(MIN(p),p)))), Z,LAMBDA(x,y,FILTER(x,BYROW(x,LAMBDA(i,AND(ISNA(XMATCH(i,y))))))), F,LAMBDA(F,x,[v],LET(j,W(x),IF(ISERROR(j),v, F(F,Z(x,j),IF(ISOMITTED(v),j,VSTACK(v,j)))))), h,INDEX(b,F(F,d)), HSTACK(h,"和"&BYROW(h,SUM),"差"&BYROW(h,LAMBDA(i,MAX(i)-MIN(i)))))
（んなっと） 2024/04/03(水) 13:12:50
[ 一覧(最新更新順) ]
YukiWiki 1.6.7 Copyright (C) 2000,2001 by Hiroshi Yuki.
Modified by kazu.