[Algorithm]Toy Problem 46

11915 ワード
toy problem テキストリンク

質問:0-1 Knapsack


リュックサック充填問題(リュックサック問題)は、有名な組み合わせ最適化問題であり、以下のように定義されています.
  • の片側にリュックサックがあり、このリュックサックに入れることができる最も重い価格が規定されています.反対側には一定の価値と重量のある荷物があります.この場合、リュックサックに収容できる様々な荷物の組み合わせの中で価値のあるものと最大の組み合わせを見つける必要があります.
    • リュックサックの重量とアイテム情報を要素の配列(items)として取得し、リュックサックの最大価値を返す必要があります.
    let weight = 50;
let items = [
  [10, 60],
  [20, 100],
  [30, 120],
];
let output = knapsack(weight, items);
console.log(output); // --> 220 (items[1], items[2])

weight = 10;
items = [
  [5, 10],
  [4, 40],
  [6, 30],
  [3, 50],
];
output = knapsack(weight, items);
console.log(output); // --> 90 (items[1], items[3])

weight = 40;
items = [
  [40, 10],
  [50, 100],
  [10, 30],
];

output = knapsack(weight, items);
console.log(output); // --> 30 (items[2])

    Reference

    // naive solution: O(2^N)
// const knapsack = function (weight, items) {
//   const LENGTH = items.length;
//   function pickOrNot(idxToCheck, value, left) {
//     if (idxToCheck === LENGTH) return value;

//     const [wt, v] = items[idxToCheck];

//     if (wt > left) return pickOrNot(idxToCheck + 1, value, left);

//     return Math.max(
//       pickOrNot(idxToCheck + 1, value + v, left - wt),
//       pickOrNot(idxToCheck + 1, value, left)
//     );
//   }

//   return pickOrNot(0, 0, weight);
// };

// dynamic: O(weight * N)
const knapsack = function (weight, items) {
  let cached = Array(weight + 1).fill(0);
  items = items.filter((item) => item[0] <= weight);
  items.forEach(([wt, v]) => {
    const possible = Array(weight + 1).fill(0);
    for (let i = 1; i <= weight; i++) {
      possible[i] = cached[i];
      if (i - wt >= 0 && cached[i - wt] + v > cached[i])
        possible[i] = cached[i - wt] + v;
      if (cached[i - 1] > cached[i]) possible[i] = cached[i - 1];
    }
    cached = possible;
  });
  return cached[weight];
};
    LeetCode: Squares of a Sorted Array
    Linuxコンポーネントパッケージ(四)RAII技術を用いてMutexLock自動化ロック解除を実現