組み合わせ問題のアルゴリズム

質問

あらかじめ用意された整数を足して、その合計がある指定された整数と等しくなる組み合わせの数を調べるプログラムを書こうとしているのですが、苦労しています。

具体例がないと伝わりにくいかもしれないので例をあげると、
例えばあらかじめ用意された整数というのが
1・1・2・2・5・8　の4つで、
指定された整数が10である場合は、
8と2
8と1と1
5と2と2と1
という3通りの組み合わせがあるので、3を出力したいというわけです。

今まではもっと単純なアルゴリズムしか考えてこなかったので、こういった組み合わせのような問題が難しく感じられます。
こういう場合、アルゴリズムはどのようなものが考えられるでしょうか。
よろしくお願いします。

回答No.2

rabbit_cat · ベストアンサー

何か上手い手を考え付かないんだったら、バックトラック法でしょうね。完全な総当りよりは、かなり計算量を減らせるはずです。
バックトラックは再帰で実装すると簡単です。（メモリ食うけど）

お礼

バックトラックというのは初めて聞く言葉です。
少し調べてみたら、おっしゃる通り再起関数をうまく使う必要があるようですね。
参考になります。ありがとうございました。

回答No.3

himajin100000

//C#で書く。総当り。

using System;
using System.Collections.Generic;

//ソースがやけに見づらいのは
//http://d.hatena.ne.jp/akkt/20080424/1209051266
//の1を努力しようとしたから。挫折したけど。

//回答にはしないけど気力が沸いたらもっとクラスに分割して，50行に収めるかも。
//特にNumberListは独自のクラスで分割できそうだし。

namespace Q4304402B
{
class Q4304402B
{

private List<int> NumberList;
private List<List<int>> AnswerList;

public Q4304402B(){

NumberList = new List<int>();
AnswerList = new List<List<int>>();

NumberList.AddRange(new int[]{1,1,2,2,5,8});
//例)
//i =13(2進数で001101)の時，
//1 * 0 + 1 * 0 + 2 * 1 + 2 * 1 + 5 * 0 + 8 * 1の総和を求める。
//それが10ならばリストに追加
//iを0からMath.Pow(2,6) - 1 = 63まで変化させる
for(int i = 0;i < Math.Pow((double)2,(double)NumberList.Count) ; i++){
Test(i);
}

}

private List<int> GetNumbers(List<int> list1){
List<int> list = new List<int>();
if (NumberList.Count != list1.Count){
throw new ArgumentException();
}
for (int i = 0;i < list1.Count;i++){
if (list1[i] == 1){
list.Add(NumberList[i]);
}
}
return list;

}

//引数の10進数を2進数をcount ビットで表現し
//各ビットのint値をリストに追加し，そのリストを返す。
private List<int> GetFlags(int count,int i){
List<int> list;
list = new List<int>();
for (int j = 0;j < NumberList.Count;j++){
list.Add(( i >> j ) % 2);
}
return list;
}

//listに入っているintの合計を求める。
private int GetSum(List<int> l1){
int x = 0;
foreach(int i in l1){
x += i;
}
return x;
}
private void Test(int i){
List<int> list = GetNumbers(GetFlags(NumberList.Count,i));
if ((GetSum(list) == 10) && IsAddable(list)){
AnswerList.Add(list);
}

}

//既にリスト中に同じ構成要素からなるものが存在しないため，
//答えとして有効。
//たとえば，既にAnswerListに{1,2,2,5}となるようなものが存在するとき，
//仮引数listが{1,2,2,5}ならfalse,{1,1,8}とかならtrue
private bool IsAddable(List<int> list){
bool retval = true;
foreach(List<int> l in AnswerList){
l.Sort();
retval = retval && !CompareList(list,l);
}
return retval;
}

//個数が一致しないときはfalse;
//内容を各リストの同一インデックスの内容を比較し，
//全て一致したらtrue,そうでないときはfalseを返す。

private bool CompareList(List<int> l1,List<int> l2){
bool retval = true;
l1.Sort();
l2.Sort();
if (l1.Count != l2.Count){
return false;
}
for (int i = 0;i < l1.Count;i++){
retval = retval && (l1[i] == l2[i]);
}
return retval;

}

//答え表示用のルーチン
public void Display(){
Console.WriteLine(AnswerList.Count);
// foreach(List<int> list in AnswerList){
// DisplayItem(list);
// System.Console.WriteLine("=================");
// }

}

//Displayメソッドで使用しようかと思ったけど，
//求められているのは個数なので封印。
private void DisplayItem(List<int> list){

foreach(int i in list){
System.Console.WriteLine(i);
}

}
public static void Main(){
Q4304402B o1 = new Q4304402B();
o1.Display();
System.Console.ReadKey(true); //キー押すまで待機
}

}

}

お礼

わざわざコードまで書いていただいてありがとうございます。
Cは使ったことがないので理解しているとは言い難いのですが、コメントも参考にさせていただきながら解釈していこうと思います。

回答No.1

neKo_deux

> 組み合わせの数を調べる

近似解を許さないのなら、総当りするしかないのでは？

質問者さんが思っているような、単純なアルゴリズムで良いと思います。

お礼

回答ありがとうございます。
計算量が少なくなるというバックトラック法を先に試してみたいと思います。