技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1つ、二次元配列

1、状態遷移方程式：

• アイテムを置かないでください : dp[i - 1][j] から推定、つまりバックパックの容量が j でアイテム i の最大値が入っていない このとき、dp[i][j] は dp[i - 1][j]。 （実際には、アイテム i の重量がバックパック j の重量よりも大きい場合、アイテム i はバックパックに入れられないため、バックパック内の値は以前と同じになります。）
• アイテム i を入れます: dp[i - 1][j -weight[i]] から推定され、dp[i - 1][j -weight[i]] は、容量が j -weight[ の場合、アイテム i を除いたバックパックの最大容量です。 i] value、dp[i - 1][j -weight[i]] + value[i] (アイテム i の値) は、アイテム i をバックパックに入れることによって得られる最大値です

したがって、再帰式は次のようになります。 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j -weight[i]] + value[i]);

2. 初期化

(1) dp[i][j]の定義から始めて、バックパックの容量jが0、つまりdp[i][0]の場合、どのアイテムを選択しても、バックパックの合計値は次のようになります。 0.

(2) 状態遷移方程式 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j -weight[i]] + value[i]); i は i-1 から導出されることがわかり、i が 0 のときに初期化する必要があります。

dp[0][j]、つまりiは0、アイテム番号0を格納する場合、各容量のバックパックが格納できる最大値です。

次に、j <weight[0] の場合、バックパックの容量は番号 0 のアイテムの重量よりも小さいため、dp[0][j] は 0 になるはずであることは明らかです。

j >= Weight[0] の場合、バックパックの容量はアイテム番号 0 を保持するのに十分であるため、dp[0][j] は value[0] である必要があります。

for (int j = 0 ; j < weight[0]; j++) {
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

(3) その他の添え字の初期化:

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 重み[i]] + 値[i])

dp[1][1] = max(dp[0][1], dp[0][1-weight[i]] + value[i]) はその左上になければなりません。

したがって、初期化されている必要があり、便宜上、デフォルトでは 0 に初期化されます。

2. 1 次元 (ローリング配列)

1. 1 次元 dp 配列において、dp[j] は次のことを意味します。容量 j のバックパックは、最大値 dp[j] のアイテムを運ぶことができます。

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

2. 初期化

(1) 容量 0 のバックパックが運ぶアイテムの最大値は 0 であるため、dp[0]=0 となります。

(2) 項目の値が 0 より大きいと仮定します。初期値で上書きされないように、だからdp配列の初期化の場合、最初はすべて 0

3. 走査順序

逆の順序でトラバースします

説明 1: リストの末尾の値は、前のレベルをトラバースして取得した前の値と比較することによって決定する必要があります。

説明 2: 各バックパックには 01 バックパックが 1 つだけあり、このバッグが配置されているかどうかは、前のバッグのステータスを表す数量と、その上の番号に関係します。右側は現在のバッグの保留ステータスです。コードでは、右側の配列を決定するために左側の数値が必要であるため、右側の数値が計算される前に左側の数値を破棄することはできません。

説明 3: 2 次元の場合、新しい dp 数値のそれぞれの結果は上と左から来ます。実際、これは 1 次元の場合に当てはまりますが、1 次元ではまだ左から右です。私の実際の左の数値が更新されました（左側はもはや「元の」左側ではありません。これにより二重カウントが発生します )、トップが元のトップのままであっても、取得される番号は正しくありません。バックパック レイヤー (内側のレイヤー) を右から左にトラバースすると、左側の要素は常に前回の操作により、新しい値で上書きされることはありません。, 正しい値を取得できるようになります。

3. アプリケーション

1. 正の整数のみを含む空でない配列を指定します。この配列を 2 つのサブセットに分割して、2 つのサブセットの要素の合計が等しくなるようにすることはできますか?

注: 各配列の要素は 100 を超えず、配列のサイズは 200 を超えません。

例 1:

• 入力: [1、5、11、5]
• 出力: true
• 説明: 配列は [1, 5, 5] と [11] に分割できます。

分析します:

そのアイテムは私です、

重みは nums[i]、値も nums[i]、バックパックの体積は sum/2 です。

01バックパックに似ている

状態遷移方程式:

dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

// 开始 01背包
for(int i = 0; i < nums.size(); i++) {
    for(int j = target; j >= nums[i]; j--) {
        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    }
}
// 集合中的元素正好可以凑成总和target
if (dp[target] == target) return true;

2. 石の山があり、それぞれの石の重さは正の整数です。

各ラウンドで、任意の 2 つの石を選択し、それらを一緒に粉砕します。石の重量が x と y、x <= y であるとします。この場合、破砕によって考えられる結果は次のとおりです。

x == y の場合、両方の岩は完全に粉砕されます。

x != y の場合、重さ x の石は完全に粉々になり、重さ y の石は新しい重さ yx になります。

結局、石はせいぜい1つしか残らない。この石の可能な最小の重量を返します。石がなくなった場合は0が返されます。

例：

• 入力: [2,7,4,1,8,1]
• 出力: 1

分析します:

石を同じ重さの 2 つの山に分割して、衝突後に残る石が最小になるようにしてください。

次に、それを 2 つの石の山に分割します。一方の石の山の合計重量は dp[目標]、もう一方の山の合計重量は合計 - dp[目標]です。

target を計算する場合、切り捨てられるため target = sum / 2 となるため、sum - dp[target] は dp[target] 以上である必要があります。

この場合、衝突後に残る石の最小重量は (sum - dp[target]) - dp[target] となります。

for (int i = 0; i < stones.length; i++) {
//采用倒序
    for (int j = target; j >= stones[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
    }
}
//结果
sum - 2 * dp[target];

から引用：コードランダムノート