『L・DK』上白石萌音&杉野遥亮インタビュー!

いつもお世話になっております。
過去にも同様の質問がありましたが、ナップザック問題について教えていただきたく思います。

エクセルのA列に50個程の数値(千円単位~1千万円単位)が入っています。
その中のどれかを足し合わせて、特定の数字を探したいのです。
(求めたい数字21,069,182)

(例)
10
5 
12

なら、15になるのは10と5の組み合わせで、10と5を求めるような感じです。

過去の質問を読み、エクセルのVBAをコピーしてやったりしましたが、フリーズしてしまったり、オーバフローなどになってしまいます。
50個と数字が多いのが問題なのでしょうか・・・

何か良い方法がございましたら、ご教授いただきたく思います。
よろしくお願いします。

このQ&Aに関連する最新のQ&A

A 回答 (7件)

一介の服飾デザイナですが、パッと思い付いたアルゴリズムは次のようです。



まず、クイックソートでもバブルソートでも構わないので昇順に並べます。

2,5,10,12

2+5---------------7 (7+5=12 next)
2+5+10------------17 (stop)

2+10--------------12 (2+10+10=22 Stop)

2+12--------------14 (Stop)

5+10--------------15 hit

10----------------10 (10+10 Stop)

次に、小さい数字から順次足していきます。
次を加算するのは、同じ数字を足して目的値に等しいか以下である場合。
もちろん、結果オーバーしていれば即抜けます。

次を加算するべきか否かは、最初の1個でも判定する必要があります。
そうすれば、10以上はテストする必要がないことが判ります。

プログラマでも何でもないので参考程度にして下さい。
    • good
    • 0
この回答へのお礼

ご回答ありがとうございます。

例がちょっと言葉足らずであったかもしれませんが、
二つの数字のみで答えが出るとは限らないんです。
50個の数値のうち25個足して数字が出るか
あるいは40個足して数字が出るか・・・

この場合、難しいですよねぇ・・・

お礼日時:2007/08/18 17:37

ゴミ回答をしたので、もう、少し補足しておきます。



5つの組み合わせがみつかったら、その要素同士の組合せの個数分だけチェック。

1+5->6
1+5+6->12
5+6->11

6、11、12があれば、それも組合せ。
次は、これを一つづ見つけなきゃならんですね。

まあ、しんどい話ですね。
だが、これで Husky流のアルゴリズムは見えてきたと思います。
なお、軽々な回答、お詫びしておきます。
    • good
    • 0

総当り法・・・なるほどですね。


私の書いたコードは、さらに、修正しなきゃならんですね。

私が見つけているのは、最も、多い要素での組み合わせ。
次は、それより1個少ない組み合わせを見つけにゃならんですね。
そういう意味では、次のループは最初の検索のそれ。

総当り法・・・なるほどですね。
酒飲みながら書くようなコードじゃなかったですね。
反省!
    • good
    • 0

総当り法のコードを眺めてみました。


事前に昇順ソートされていないデータを総当りしている感じですね。
問題は、コードを真似るのではなくアルゴリズムを理解すること。
例えば、クイックソートのアルゴリズムを理解するのに私はカードを使いました。
「あー、なるほど。このような要領で並び替えているのか」
コードを書くというのは、決して、知的な作業ではないです。
一旦、アルゴリズムを理解してしまえば、コード書きは単なる肉体労働です。
先ずは、アルゴリズムを「ガッテン!」と思うまで解読されたし。

なお、私の回答は、組み合わせは求めることが可能。
だが、エクセルのどのセルかには答えられません。
しかし、値と取り込む際に、10,20,15,234 を 10.01, 20.02,15.03,234.04と変換して取り込めば、それも可能です。
    • good
    • 0

ちょっと、回答に自信がなかったのでコードを書いてみました。


確かに、100になる組み合わせを見つけました。
もちろん、素人が酒飲みながら書いたコード。
ちゃんと URL のやり方を参照されて下さい。

[イミディエイト]
10, 15, 20, 25, 30,

Private Sub Command1_Click()
  Dim H     As Integer
  Dim I     As Integer
  Dim N     As Integer
  Dim M     As Integer
  Dim Target  As Integer
  Dim Amount(9) As Long
  Dim strUnit  As String
  
  Amount(0) = 10: Amount(1) = 20: Amount(2) = 30: Amount(3) = 40: Amount(4) = 50
  Amount(5) = 45: Amount(6) = 35: Amount(7) = 25: Amount(8) = 15: Amount(9) = 5
  ' ------------
  ' 昇順ソート
  ' ------------
  QSort Amount(), 0, UBound(Amount())
  ' ----------------------------------
  ' 100 になる組合せを求める
  ' ----------------------------------
  Target = 100
  For I = 0 To 9
    strUnit = Str(Amount(I)) & ","
    M = Amount(I)
    H = I + 1
    If M = Target Then
      Debug.Print strUnit
    ElseIf M * 2 <= Target Then
      For J = H To 9
        M = M + Amount(J)
        strUnit = strUnit & Str(Amount(J)) & ","
        If M = Target Then
          Debug.Print strUnit
          Exit For
        ElseIf M + Amount(J) > Target Then
          Exit For
        End If
      Next J
    End If
  Next I
End Sub

Public Sub QSort(ByRef Datas() As Long, ByVal intTop As Integer, ByVal intLast As Integer)
  Dim I As Integer
  Dim J As Integer
  Dim R As Integer
  Dim N As Integer
  Dim Temp As Long
  Dim Part As Long

  N = intLast - intTop + 1
  If N < 2 Then
    Exit Sub
  End If
  Part = Datas(intTop + Int(N / 2))
  I = intTop - 1
  J = intLast + 1
  Do
    Do
      I = I + 1
    Loop While Datas(I) < Part
    Do
      J = J - 1
    Loop While Datas(J) > Part
    If (I < J) Then
      Temp = Datas(I): Datas(I) = Datas(J): Datas(J) = Temp
    End If
  Loop Until (I >= J)
  R = N - I
  QSort Datas(), 0, I - 1
  QSort Datas(), I, I + R - 1
End Sub
    • good
    • 0
この回答へのお礼

ご回答ありがとうございます。

URLの方法を参考にしながらやってみましたが、フリーズしてしまって先に進めない状態です。
20個位の少ない数字なら大丈夫なんでしょうけど、50個もあり、
しかも桁が多い場合は時間ばかりかかり答えを求めるのは不可能なようですね・・・

お礼日時:2007/08/19 20:32

そのナップザック問題に関しては無知ですが、2個でも30個でも同じじゃないですかね。

    • good
    • 0

どのようなVBAを試されたのか分からないのですが、総当たり法では2^50-1通りの計算が必要になり、EXCELの有効桁数を超えてしまいます。

下記URLの動的計画法をお試しになってはいかがでしょうか。
(既にお試しなら読み飛ばしてください)

ただし時間がかかるのは覚悟してください。フリーズと見えても本当に計算中なのだと思いますよ。

http://www.geocities.co.jp/SiliconValley-Oakland …
    • good
    • 0
この回答へのお礼

ご回答ありがとうございます。

動的方法を試しましたが、やはりフリーズしてしまいました。
メモリが少ないので、50個の数値は厳しいです・・・

お礼日時:2007/08/19 20:23

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qエクセルで決められた合計になる組み合わせを作成

エクセルを使用し、決められた合計になるような数値の組み合わせを表示するようにしたいのですが、どのようにしたらよいか皆さん教えて下さい。
例えば、
B列に
100・50・70・62・58・70・・・と数値が入力されています。
C1に300と入力しておきます。
300になる組み合わせはどれとどれ・・・なのかというものを作成したいです。
多数ある場合は、全ての組み合わせを表示したいです。
表示例として
B3とB5とB15・・・を合わせると合計C1が300になる、又は298又は302になるという表示をしたいのですがどのようにしたらよいでしょうか。
A列にコードを入力しているので数値の重複はありません。
宜しくお願い致します。

Aベストアンサー

総当りで組み合わせを試し、その合計が与えられた数字と一致するかどうかを調べるプログラムを書くことになります。

なお、20項目くらいまでは何とか実用的に使えますが、30項目を超えると条件によっては総当りを試すのに数年かかる可能性があります。現実的な時間内に必ず回答が得られるようなプログラムを作成することはできません。

Qエクセルでの組み合わせ出力方法(計算含む)

エクセルの初心者です。
エクセルで作成した数字の表を利用して、その表の中の任意の数字の組み合わせの合計が、ある数字ぴったりの組み合わせを探し出すにはどうすればいいでしょうか?表の数字は50くらいあります。

Aベストアンサー

ご希望の操作は、50個のセルに入力されている値の中からいくつかの数字を選択して、その数字の合計が特定の値になる組み合わせを探したいということでしょうか?

その場合はソルバーの機能を利用します。

たとえばA1からA50セルに任意の数字が入力されている場合、C1セルに「=SUMPRODUCT(A1:A50,B1:B50)」と入力しこのセルを選択しておき、「ツール」「ソルバー」(表示されない場合は「アドイン」からソルバーにチェックを入れます)から、目標値の「値」の欄にチェックを入れ、合計する目標数字を入力し、変化させるセルの欄は「B1:B50」セルを選択し、制約条件で「追加」ボタンを押し、左側の欄に「B1:B50」セル、真ん中を「データ」にして「OK」します。
条件を入力したら「キャンセル」して元のダイアログを表示して、「OK」します。

これで目標値が見つかりましたと表示された場合、B列に1と表示されているA列の数字の組み合わせが、求める組み合わせデータとなります。

QExcelでの全通りの組み合わせ出力方法(文字列)

Excelについて全くの初心者で、教えて頂きたい質問があります。

Excelの文字列の全通りの組み合わせを出力がしたいのですが、その方法が分かりません。
例えばセルAに
・りんご
・みかん
・いちご

セルBに
・だいこん
・キャベツ
・トマト

があり、別のセルにその全通りの組み合わせを出力
(文字と文字の間はスペース)

りんご だいこん
りんご キャベツ
りんご トマト
みかん だいこん
みかん キャベツ
みかん トマト
いちご だいこん
いちご キャベツ
いちご トマト

この様に出来る方法はあるでしょうか?
また出来ればその裏(だいこん りんご)も出力したいと考えており、キーワードは3つまで出来るようになりたいです。

どなたかご存じでしたら、ぜひお教え下さい。
よろしくお願いします。

Aベストアンサー

A列B列は1行目からデータがあるものとします。
C列に転記するものとします。

以下の手順をおためしください。

1.Altキー+F11キーでVisualBasicEditorを呼び出します。

2.メニューから挿入、標準モジュールで出てきたコードウィンド(右側の白い広い部分)に以下のコードをコピペします。

Sub test01()
a = Cells(Rows.Count, "A").End(xlUp).Row 'A列最終行取得
b = Cells(Rows.Count, "B").End(xlUp).Row 'B列最終行取得
For i = 1 To a '1行からA列最終行まで繰り返し
For n = 1 To b '1行からB列最終行まで繰り返し
x = x + 1
Cells(x, "C") = Cells(i, "A") & " " & Cells(n, "B") 'C列に結合して転記
Next n
Next i
End Sub

3.Alt+F11キーでワークシートへもどります.

4.メニューから、ツール、マクロ、マクロで出てきたマクロ名(test01)を選択して実行

これでできます。
これがわかれば「裏」というのも簡単ですよね。
以上はVBAでの回答ですが、外していたらごめんなさい。

A列B列は1行目からデータがあるものとします。
C列に転記するものとします。

以下の手順をおためしください。

1.Altキー+F11キーでVisualBasicEditorを呼び出します。

2.メニューから挿入、標準モジュールで出てきたコードウィンド(右側の白い広い部分)に以下のコードをコピペします。

Sub test01()
a = Cells(Rows.Count, "A").End(xlUp).Row 'A列最終行取得
b = Cells(Rows.Count, "B").End(xlUp).Row 'B列最終行取得
For i = 1 To a '1行からA列最終行まで繰り返し
For n = 1 To b '1行...続きを読む


人気Q&Aランキング

価格.com 格安SIM 料金比較