Knapsackアルゴリズム

1309 ワード
Knapsack テキストリンク
シェーディングアルゴリズムは有名なDPアルゴリズムの一つである.
タイプは2種類に分けられます.

Fraction Knapsack


物の値段を重さに分けて、重さが値段より高い順に並べて入れると、簡単に解決できます.荷物の重さが残りのリュックサックが耐えられる重さを超えていれば、切って入れることができます.
->Greedyソリューション

0-1 Knapsack


物を切ることができないので、物の重さ、物の値段、リュックサックの残容量はすべて考慮しなければなりません.
->DPで解決可能
パッケージ中の最大装着可能Mkgの場合、dp[i][j]=パッケージ中のアイテムの重量の和がiの場合、最初のjアイテム中の装着可能な最大値(1 iが現在の物品の重量wより小さい場合
現在積み込みができないため、古い値をコピーします.
dp[i][j] = dp[i][j-1]
  • iが現物の重量w以上である場合
    今は荷物を入れることができます.
    物を詰める時と、物を入れていない時の価値を比較してから、もっと高い値段を割り当てます.
    今のものの価値はvです.
    • dp[i][j] = max(dp[i][j-1], dp[i-w][j-1] + v)
    最終的に,物品の最大価値はdp[パッケージサイズ][物品個数]で求めることができる.
    Boottom-Up重複除外
    for (int i = 1; i <= N; i++) {
	// K부터 탐색하여 담을 수 있는 무게 한계치가 넘지 않을 때까지 반복 
	for (int j = M; j - w[i] >= 0; j--) {
		dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
	}
}
    実装時には、最初の円のメモリ性能も良好であるため、dpを2次元に設定する必要はない.

    リファレンス


    シェーディングアルゴリズムの3つの解法
    シェーディングアルゴリズム
    10.24便42日間TIL
    overlayfsとDockerの関係性(実装も少しだけ見てみる記事)