問題タブ [subset-sum]

これはインタビューの質問です：

4 人の男性 - それぞれ 1、3、7、10 分で橋を渡ることができます。一度に橋を渡ることができるのは 2 人だけです。彼らが橋を渡るのに何分かかりますか。

解決策を次のように手動で考えることができます: 10 と 7 が一緒になり、7 が目的地に到達するとすぐに「3」がホップインし、10 と 3 が一緒に完了します。1 は自然に進み、合計所要時間は 11 です。したがって、{10, 7} の後に {10, 3} が続き、その後に {1} が続きます。

これを一般的なアルゴリズムのコードに実装する方法を考えることができません。このアイデアを実際のコードに変換する方法を特定するのを手伝ってくれる人はいますか?

sumsubsetproblem についてwiki http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solutionを読み、次の問題に適応できるかどうか疑問に思います。

n1 によって制限されたすべての可能なサブセット ss1、ss2 が必要です。n2 は 2 つのセット s1、s2 からの要素の数です。

S1 の要素を正の要素として使用し、s2 の要素を負の要素として使用して、サイズ n1 と n2 のサブセットの合計が 0 であるかどうかという質問に答えます。

ここでの私の特別な問題は、セットに 0 自体を含めることができることです。これらの要素をそれぞれ 1 または -1 に設定することでこれを解決できると思いました (1 は私の入力のメンバーではなく、(0,10,50,100,200,500) になります)。次の問題は、このアルゴリズムが私に「はい」か「いいえ」しか与えないことですが、私はこの答えをすでに知っています (前提条件です) 必要なのは結果です。

これはまだ十分に速いですか？OPがランタイムのリストを投稿したperl実装についてここで読んだことがあります.30要素の計算時間は30〜40秒で、私のニーズには遅すぎます.Javaで実装する必要があります.私が知っているように、perlよりもさらに遅い

よろしく

ダーク

S1 の要素の合計 = S2 の要素の合計である集合 S の素集合 S1 と S2 (S1 U S2 は S ではない可能性があります) のペアがいくつ存在するかを計算したいと思います。

考えられるすべての 2^n サブセットのすべてのサブセット合計を計算したとします。合計が等しいばらばらの部分集合の数を調べるにはどうすればよいですか?

合計値 A の場合、これを解くために合計 A/2 を持つサブセットの数を使用できますか?

例として: S ={1,2,3,4}

可能なさまざまな S1 および S2 セットは次のとおりです。

S1 = {1,2} および S2 = {3}

S1 = {1,3} および S2 = {4}

S1 = {1,4} nd S2 = {2,3}

問題へのリンクは次のとおりです 。 http://www.usaco.org/index.php?page=viewproblem2&cpid=139

nXn 行列が与えられます。以下に示すように、さまざまな形状/サイズのオブジェクトがいくつかあります。グリッド上のすべてのオブジェクトを効率的にバインドするにはどうすればよいですか?

形状は次の画像のとおりです。

「バインド」とは、オブジェクトを nXn グリッドに配置することを意味します。オブジェクトのサイズは 1、2、... 最初の 7 つのサイズの形状が画像に示されています。