問題タブ [dynamic-programming]

n3 次元のボックス ( h、w、 )が与えられますd。目標は、最大の高さになるようにそれらを積み重ねることです (ボックスを回転させることができます)。上に置く各ボックスの寸法 ( w、d) は、下のボックスよりも小さくする必要があります。

動的計画法と貪欲でどのようにそれを行うことができますか?

これが最大 L 合計に関する私の最初の質問です。

問題: mxnの 正の整数行列が与えられた場合、1 行目から m 行目までの L の合計の最小値を見つけます。L(4 項目) チェスの馬の動きが好き

例 : M = 3x3

0 1 2

1 3 2

4 2 1

可能な L の動きは次のとおりです: (0 1 2 2), (0 1 3 2) (0 1 4 2)

私はこれを動的プログラミングで解決しました。これが私のアルゴリズムです:

1. mxn の別の Minimum L Moves Sum 配列を取得し、メイン マトリックスの最初の行をコピーします。私はそれを (MLMS) と呼んでいます 2.最初のセルから開始し、L の動きを調べて計算し
ます 3.存在する値よりも小さい場合は MLMS に挿入します4.
ステップ2 を実行します. m 番目の行まで5.最小値を選択しますm行目の合計

私の例を段階的に説明しましょう：

1. M[ 0 ][ 0 ] sum(L1 = (0, 1, 2, 2)) = 5 ; 合計 (L2 = (0,1,3,2)) = 6; したがって、MLMS[ 0 ][ 1 ] = 6
   sum(L3 = (0, 1, 3, 2)) = 6 ; 合計 (L4 = (0,1,4,2)) = 7; したがって、MLMS[ 2 ][ 1 ] = 6
   

2. M[ 0 ][ 1 ] sum(L5 = (1, 0, 1, 4)) = 6; 合計 (L6 = (1,3,2,4)) = 10; したがって、MLMS[ 2 ][ 2 ] = 6
   

   ... 最後の MSLS は次のとおりです。
   0 1 2
   4 3 6
   6 6 6
   これは、6 が 0 から m まで到達できる最小 L 合計であることを意味します。

O(8*(m-1) n) = O(m n)だと思います。この問題に適合する最適なソリューションまたは動的計画法アルゴリズムはありますか?

ありがとう、長い質問でごめんなさい

これが動的計画法としてタグ付けされた問題です（数Nが与えられ、2つ以上の連続する整数の合計としてそれを書く方法の数を見つけます）そして例15 = 7 + 8、1 + 2 + 3 + 4 + 5、4 + 5 + 6

私はそのような数学で解決しました：

a +（a + 1）+（a + 2）+（a + 3）+ ... +（a + k）= N

（k + 1）* a +（1 + 2 + 3 + ... + k）= N

（k + 1）a + k（k + 1）/ 2 = N

（k + 1）*（2 * a + k）/ 2 = N

次に、Nが（k + 1）と（2 * a + k）で割り切れる場合、O（sqrt（N））時間で答えが見つかることを確認します。

これが私の質問です。動的計画法によってこれをどのように解決できますか？複雑さ（O）は何ですか？

PS：質問が重複している場合は、すみません。検索しましたが見つかりました

KnapsackDPで解決できる一方で、NP完全であることはわかっています。pseudo-polynomial彼らは、「入力の長さ」（つまり、入力をエンコードするために必要なビット数）が指数関数的であるため、DPソリューションは であると言います。残念ながら、私はそれを取得しませんでした。誰pseudo-polynomialか私にそのことをゆっくり説明してもらえますか?

ここからの問題です

ACM International Collegiate Programming Contest Asia Regional Contest, 横浜, 2006-11-05

x から始めて を繰り返し掛けると、30 回の掛け算でx計算できます。x^31

与えられた正の整数x^n から始まる乗算と除算によって計算する演算の最小数を見つけるプログラムを作成し、xnn<=200

n = 31 の場合、最小操作数は 6
n = 50 の場合、最小操作数は 7

どんなアイデアでも大歓迎です。

S=5およびN=3とすると、解は次のようになります-<0,0,5> <0,1,4> <0,2,3> <0,3,2> <5,0,0> < 2,3,0><3,2,0><1,2,2>など。

一般的なケースでは、N個のネストされたループを使用して問題を解決できます。N個のネストされたループを実行し、その中でループ変数がSになるかどうかを確認します。

事前にNがわからない場合は、再帰的なソリューションを使用できます。各レベルで、0からNまでのループを実行してから、関数自体を再度呼び出します。深さNに達したら、得られた数の合計がSになるかどうかを確認します。

他の動的計画法ソリューションはありますか？

私は次の問題を解決するための最良の方法を見つけようとしています。最善の方法で、私はそれほど複雑ではないことを意味します。

入力として、次のようなタプル（start、length）のリスト：

各要素は、開始と長さ(5,6,7,8,9,10,11)によってシーケンスを再プリセットします。たとえば、（5,7）は、シーケンス（ 5で始まる7つの要素のリスト）と同等です。タプルはstart要素によってソートされていると見なすことができます。

出力は、最長の連続シーケンスを表すタプルの重複しない組み合わせを返す必要があります。つまり、ソリューションは、オーバーラップやギャップのない範囲のサブセットであり、可能な限り最長です。ただし、複数存在する可能性があります。

たとえば、与えられた入力の場合、解決策は次のとおりです。

[(0,5),(5,7)]に相当(0,1,2,3,4,5,6,7,8,9,10,11)

この問題を解決するための最良のアプローチをバックトラックしていますか？

私は人々が提案できるさまざまなアプローチに興味があります。

また、誰かがこの問題または同様の別の問題の正式な参照を知っている場合は、参照を取得したいと思います。

ところで-これは宿題ではありません。

編集

いくつかの間違いを避けるために、これは予想される動作の別の例です

[(0,1),(1,7),(3,20),(8,5)]正解のような入力の場合、[(3,20)]長さ20の（3,4,5、..、22）と同等です。受け取った回答の一部は[(0,1),(1,7),(8,5)]（0,1,2、...、11,12）と同等になります。正解として。しかし、はより短いため、この最後の答えは正しくありません[(3,20)]。

C# で動的プロキシを作成する必要があります。このクラスで別のクラスをラップし、そのパブリック インターフェイスを使用して、これらの関数の呼び出しを転送する必要があります。

使用方法は次のとおりです。

生産する:

何か案は？

これを行う最も簡単な方法は何ですか?

これを行う最善の方法は何ですか？

本当にありがとう。

アップデート

Wernight の推奨に従い、C# 4.0 動的プロキシを使用してこれを実装しようとしました。残念ながら、私はまだ立ち往生しています。プロキシのポイントは、(通常、通常) 期待される他のインターフェイスを模倣することです。DynamicObject を使用するには、このすべてのクライアントを変更して、「ISecondaryInterface」ではなく「dynamic」を使用する必要があります。

A をラップするときに、A のインターフェイスをサポートしていることを (静的に?) アドバタイズするように、プロキシ オブジェクトを取得する方法はありますか。Bをラップすると、Bのインターフェースをサポートしていることをアドバタイズしますか?

更新 2

例えば：

ここに問題があります

1≤N≤50の番号が与えられます。すべてのチケットには2N桁の番号があります。最初のN桁の合計が最後のN桁の合計と等しい場合、チケットをラッキーと呼びます。また、番号のすべての桁の合計が与えられます。あなたの仕事は、すべての桁の指定された合計を持つラッキーナンバーの量を数えることです。

入力22の場合、出力は4（0101、0110、1001、1010）です。

この問題を解決するのを手伝ってもらえますか？最小の複雑さはどれくらいですか？

明日は、オンラインのGoogleテストを新しいものとして作成します。どうやら、彼らは間違いなく動的計画法に関する1つの問題を尋ねていますか？

解決策とともにCのDP問題を収集するための優れたリソースを知っている人はいますか？私はDPが何であるかを知っており、1、2回使用したことがあります。ただし、テストでDPの問題を解決するように感じますが、一般的な問題を事前に実践しておくと、アプローチが容易になります。

Cのソリューションに関する優れたリソースや問題セットは高く評価されます。ありがとう。