整数resultと整数の配列があるとしましょう[a,b,c]（固定長ではありません）。を検出する必要がありresult=a*i +b*j + c*kますi,j,k>=0。
可能であれば、C/C# でのソリューションを好みます。
PS問題は予約システムからのもので、旅行の期間が特定の期間の組み合わせである場合、旅行を販売できます。
ありがとう！
例: a=3, b=7 の場合 rezult 20 = 3*2 + 7*2 結果 9 = 3*3 + 7*0
2 に答える
6
これは、一般に NP 困難なフロベニウス問題です。
ただし、小規模なインスタンスの場合、かなり高速なアルゴリズムが知られています。
ここの論文: http://www.combinatorics.org/Volume_12/PDF/v12i1r27.pdfは、以前のアルゴリズム (Dijkstra の最短パス アルゴリズムの適用を含む!) を説明しているようです。以前のもの。
いずれにせよ、gcd(a,b) = 1 となる a と b の 2 つの数しかない場合、a i + b j = M となる i, j >= 0 を見つけるのは簡単です。
(a-1)(b-1) より大きい任意の数は、i >=0 および j>= 0 のa i + b jの形式で表すことができることも知られています。フロベニウス数は、次のように定義されます。 n >= 2 かつ gcd(a,b,c...) = 1 の場合に存在する最大数。
したがって、あなたの場合、関係する数値が十分に小さい場合は、配列をソートし、gcd(a,b) = 1 となるような「最小の」2 つの a と b を見つけて、M >(a-1)(b かどうかを確認できます。 -1)、これは a と b だけで解決できます。
M <= (a-1)(b-1) であり、a と b が十分に小さい場合、ブルート フォースでそれを排除できる可能性があります。
于 2010-05-26T12:50:28.403 に答える
0
入力ベクトルが固定長でない場合、i、j、k の可能な値は何ですか?
あなたの問題はナップザックの問題のバリエーションのように思えます。
于 2010-05-26T12:31:46.083 に答える