ナップサック問題
ある制約の中で選択肢を選んで合計が最大になるようにする目的
重さと価値
リュックを持っている
いくつかのアイテムがありそれぞれ重さと価値の特性をもっている
最大容量が決まっている中で価値の合計が最大になるように計算する
code:typescript
type Item = {
weight: number;
value: number;
};
function knapsack(items: Item[], capacity: number): number {
const n = items.length;
// DPテーブルの初期化
const dp: number[][] = Array.from({ length: n + 1 }, () =>
Array(capacity + 1).fill(0)
);
// DPテーブルを埋める
for (let i = 1; i <= n; i++) {
const { weight, value } = itemsi - 1; // 現在のアイテム for (let w = 0; w <= capacity; w++) {
if (w >= weight) {
// アイテムを選ぶ場合と選ばない場合を比較
} else {
// アイテムを選べない場合
}
}
}
// 最適解を返す
}
// 使用例
const items: Item[] = [
{ weight: 2, value: 3 },
{ weight: 1, value: 2 },
{ weight: 3, value: 6 },
];
const capacity = 5;
console.log(knapsack(items, capacity)); // 出力: 8
配列と重量を渡す
最初に2次元配列の初期化をする
アイテムを一個ずつループさせて各容量に対する最大価値を計算する
考え方
配列 dp、[i],[w] を用意します。
現在考慮中のアイテムのインデックス
現在のナップサック容量
dp[i],[w] は、「アイテム i までを考慮して、容量 w の中で得られる最大価値」を表します。
基本ルール
アイテムを選ばない場合: dp[i],[w] = dp[i-1][w]
アイテムを選ぶ場合: dp[i][w] = dp[i-1][w - weight[i]] + value[i]
この2つの値のうち、大きい方を dp[i][w] に記録します。