セット内のどの数字が別の特定の数字に加算されるかを見つける方法は？
https://stackoverflow.com/questions/1202540
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
これは、会計システムでの作業に直面していると思われる問題です。
一連のトランザクションがありますが、それらの合計は、会計部門がすべきと考える金額とは異なります。彼らは数学に疑問を投げかけているのではなく、含まれているトランザクションだけです：p
合計が所定の金額と一致するために、セット内のどのトランザクションを含めるべきではないかを判断するのに役立つアルゴリズムがあります。
Given Set:
2
4
5
7
Given Sum Amount:
13
Result Set:
2
4
7
編集： セットに含まれるトランザクションは100未満です。 NP-completeの解決にないC＃の例はありますかXKCD の質問に問題がありますか？
男、私はCS学位を取得すべきだった。
解決
これは Subset Sum の問題で、 NP-Complete 。しかし、それはサブセットの合計を見つけるためのアルゴリズムがないという意味ではありません。
他のヒント
これはナップザックの問題であり、NP-Completeです。小さな入力セットを除いて、簡単に正確に解決することはできません。適切なサイズの問題セットの場合、それはそれらの全世界の寿命から解決する問題の1つです。
そうは言っても、遺伝的アルゴリズムのナップザックソルバーがあります。
上記のメンバーが言ったように、これはサブセット和問題（またはナップザック問題）です。 ただし、効率的に実行できないと言うのはあまり正確ではありません。それはできる、ただできない 多項式時間で。このソリューションは、実際には動的プログラミングを使用して非常に簡単です および再帰（および擬似多項式時間）。
指定された整数[a_1、...、a_n]および数値T、
配列S [i、k]を定義して、間に要素のサブセットがあるかどうかを示します a_1、... a_iは合計kになります。 （これはバイナリマトリックスです。）
その後、次のように再帰的な関係を定義できます。
S [i、k] = S [i-1、k]またはS [i-1、k-a_j]
言い換えれば、これは要素a_iを使用するかしないかを意味します。 答えはS [n、T]にあります。
行列Sを構築するための作業負荷はどれくらいですか？ さて、Sにはn * T個の要素があります。各要素を計算するには、 O（1）の作業を行う必要があります。したがって、完全な実行 時間はO（n * T）です。
この時点で、P = NPが証明されたようです。 多項式時間アルゴリズムのようです。ただし、覚えておいてください 入力サイズをバイナリで測定するため、T = 2 ^ p p。
上記の解決策を誰も言うとは思わない 適切に実装するのは理不尽です。実際、多くの人にとって 合理的な問題サイズ、見事に実行されます。
また、この問題を解決するためのいくつかのヒューリスティックがありますが、私は その分野の専門家ではありません。
これは、ナップザックの問題のバージョンです。 NPは完全なため、一般的な答えは得られません。トランザクションのセットはどれくらいの大きさですか？あなたが示したのは5ですか、それとも500ですか？
OK。多くの人々が問題の名前を与えて、NPがそれが難しいことに言及しました。そして一般的に、それらは正しいです。ただし、解決する必要がある非常に具体的なケースがあります。最初に尋ねる質問は、100件の取引が正しい取引に近いと思うかどうかです。合計があります（「合計」）。彼らはいくつかの合計を持っています。 （「実際の」合計）。したがって、トランザクションの一部は偽物です。偽のトランザクションがほんの少ししかないと思われる場合、これはそれほど悪くはありません。たとえば、偽のトランザクションが1つしかない場合を考えてみましょう。その場合、100個の異なる番号をチェックするだけで済みます。偽のトランスが2つある場合、100 * 99の小切手を見ていて、4つの偽のトランスでほぼ100,000,000ステップで物事が狂っています。ただし、実行しているのがintの追加だけであれば、それほどひどいことではありません。
もう1つの可能なショートカットは、データの性質を調べることです（偶然にも、100個の「数字」と予想される合計を投稿することは可能ですか？）。実際の合計に対してあなたの合計はいくらですか？これらを削除すると、実際の合計よりも突然低くなるほど大きな値がありますか？もしそうなら、あなたはそれらの値が偽の値になり得ないことを知っています。たとえば、あなたの例では、7は絶対に必要です。
bool bBreak = false;
int iEnd = 13;
ArrayList ar1 = new ArrayList();
ar1.Add(2);
ar1.Add(4);
ar1.Add(5);
ar1.Add(7);
String s1 = " ";
foreach (int i in ar1)
{
if (i == iEnd)
{
s1 = "Result = " + i;
bBreak = true;
}
if (bBreak) break;
ArrayList ar2 = new ArrayList();
ar2.AddRange(ar1);
ar2.Remove(i);
foreach (int j in ar2)
{
if ((i + j) == iEnd)
{
s1 = "Results = " + i + ", " + j;
bBreak = true;
}
if (bBreak) break;
ArrayList ar3 = new ArrayList();
ar3.AddRange(ar2);
ar3.Remove(j);
foreach (int k in ar3)
{
if (bBreak) break;
if ((i + j + k) == iEnd)
{
s1 = "Results = " + i + ", " + j + ", " + k;
bBreak = true;
}
}
}
}
Console.WriteLine(s1);
はい、これは可能です。この投稿がまだ開かれているかどうかはわかりません。ただし、Excelソルバーアドインを実行する必要があります。隣接するセルに1を付けて、すべての数字を投稿します。次に、目的の出力番号を入力します。次に、使用されているすべての番号が隣接する「1」を保持し、未使用の番号が「0」になります。次に、「1」を持つもののみをリストするフィルター式を実行します。その横に。
