ナップザック問題？をエクセルにて解決したいです。

Excelである一定の数値（下記の「許容量」）に最も近づけつつもを超えないように
一覧の数を合計しその組み合わせを抽出したいです。
（すべてのパターンではなくても最適な1パターンでOK）

関数でもマクロでもいいので、方法をご教示いただけますと幸いです。
■■■■■■■■■■■■■■
許容量　240gの場合

A1　120g
A2　150g
A3　130g
A4　110g
A5　120g

組み合わせ
❶A1・A5
❷A3・A4
❸A2
■■■■■■■■■■■■■■

質問者からの補足コメント

• ありがとうございます。
  重視するのは処理速度だけで大丈夫です。
  具体的なコードをご教示いただけますと幸いです。

  No.1の回答に寄せられた補足コメントです。 補足日時：2022/03/18 15:40

• また、完全合致することは少ないので、
  なるべく許容量に近い組み合わせを優先で作っていくイメージになります。
  
  よろしくお願い致します。

    補足日時：2022/03/18 15:42

No.4 回答者： Qchan1962 回答日時： 2022/03/19 09:18

こんにちは

ご希望のようなVBAコードは古くからQAサイトや参考サイトに掲示されていると思います。ドンピシャが無くてもロジックが分かれば改造も容易と思いますよ。
とは言え、具体的なコードが欲しいようですので下記を参考にしてください

1点、私の中で？が付くところがあります。
❶A1・A5
❷A3・A4
❸A2
（上記が答えとして）
A２が登場するのに　なぜ　A1・A4　は登場しないのでしょうか
A2単体より240gに近いと思うのですが、、、
そのあたりがはっきりしないまま書きますのでご希望と違ていたら
修正してくださいね。追質は勘弁ね

A列に　A1・A2・A3・・・（任意の文字アイコン）
B列に　120・150・130・・・（任意の数値）
許容量はコード内
出力はD1セル以下に

ご質問の内容で作ったので他の数値で上手くいくかは、どうでしょう

Option Explicit
Sub sample()
Dim tp As Long, maxV As Long
Dim i As Long, j As Long, n As Long, k As Long
Dim x As Long, y As Integer
Dim cnt As Long, tMax As Long
Dim V(), Ary(), tmp()
maxV = 240
n = Range(Cells(1, 2), Cells(Rows.Count, 2).End(xlUp)).Count
ReDim V(n, 1)
For i = 1 To n
V(i, 0) = Cells(i, 2).value
V(i, 1) = Cells(i, 1).value
If tMax < Cells(i, 2).value And maxV > tMax Then tMax = Cells(i, 2).value
Next
For j = 1 To 2 ^ n - 1
tp = 0
cnt = 1
For k = 1 To n
If j And cnt Then tp = tp + V(k, 0)
cnt = cnt + cnt
Next
If tp <= maxV And tMax <= tp Then
tMax = tp
cnt = 1
For k = 1 To n
If j And cnt Then
ReDim Preserve tmp(1, x)
tmp(y, x) = V(k, 1)
If y = 0 Then y = 1 Else y = 0
End If
cnt = cnt + cnt
Next
x = x + 1
End If
Next
ReDim Ary(UBound(tmp, 2), UBound(tmp, 1))
For i = 0 To UBound(tmp, 1)
For j = 0 To UBound(tmp, 2)
Ary(j, i) = tmp(UBound(tmp, 1) - i, UBound(tmp, 2) - j)
Next
Next
Range("D1").Resize(UBound(Ary, 1) + 1, UBound(Ary, 2) + 1) = Ary

End Sub

No.3 回答者： fujillin 回答日時： 2022/03/18 19:02

こんばんは

一般解としては、No2様のおっしゃるソルバーを利用するのが宜しいように思います。
とは言え、ご提示のように種類数が5組程度であれば、全数の組み合わせで求めても大したことはありませんね。
（2^5＝32通りなので）

試みに、無理矢理に関数で求めてみました(笑)
・添付図のA1:A5に元となる数値があるものとします。
　（上記の数量は整数値であるものと仮定しています）
・許容量の上限がD1セル
・D3セルが得られる解の合計値
・D4セルがその際の組合せ
（下位の桁から順にA1・・A5セルに相当し、1の値部分に相当するセルを加算していることを示します）

添付図の例では「10001」なので、A1とA5を加算して240になっているということになります。
関数式として、
D3セルには、
=AGGREGATE(14,6,(MMULT((BITAND(ROW(A1:A31),{1,2,4,8,16})>0)*1,A1:A5))/(MMULT((BITAND(ROW(A1:A31),{1,2,4,8,16})>0)*1,A1:A5)-D1<=0),1)

D4セルには、
=RIGHT("0000"&DEC2BIN(MOD(AGGREGATE(14,6,(MMULT((BITAND(ROW(A1:A31),{1,2,4,8,16})>0)*1,A1:A5)+ROW(A1:A31)/1000)/(MMULT((BITAND(ROW(A1:A31),{1,2,4,8,16})>0)*1,A1:A5)-D1<=0.1),1)*1000,1000)),5)

を入力してあります。

No.2 回答者： chonami 回答日時： 2022/03/18 14:26

ソルバーでできるのでは？

https://amidagamine.com/notes/3729

No.1 回答者： ShowMeHow 回答日時： 2022/03/18 12:49

総当たりして、条件に合致するものを出すのがいいんじゃないか？

プログラムをどう作っていくかは、どういうところにポイントを置くかによって変わってくる。
・誰が読んでもわかりやすいものにしたいのか
・汎用性を高めたいのか
・処理速度を速めたいのか
・メモリなどのリソースを制限したいのか
・再帰などを試してみたいのか
・なるべくコードを短くしたいのか
・・・・・・