iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 24
1
Software Development

使用JavaScript學習資料結構與演算法系列 第 24

Day24-動態規劃-0/1背包問題

不知不覺開賽也來到第24天了,在前面的23天介紹了資料結構/排序搜尋演算法之後,剩下的7天每天都會用來解一道題目,那麼今天要探討的是一個非常經典的 Knapsack problem 背包問題,此問題描述如下:

給定一些物品和一個背包,那些物品都有各自的價值與重量,並且背包能夠容納的重量有限,那麼我們應該要選擇哪些物品放入背包又不超重,又使選擇到的物品總價值最高呢?

問題大致上的內容就是這樣,不過在實作前可以先看看這個影片,自己上網找了不少背包問題的影片,覺得這個影片講解的非常清楚,最後還用了C語言實作,語法不難理解。

https://www.bilibili.com/video/av36136952?from=search&seid=1029365489294798332

接著我們就來實作吧!

首先設定物品和背包容量:

// 物品1: 重量2,價值3,索引0
// 物品2: 重量3,價值4,索引1
// 物品3: 重量4,價值5,索引2
// 物品4: 重量5,價值8,索引3
// 物品5: 重量9,價值10,索引4
const weight = [2, 3, 4, 5, 9];
const value = [3, 4, 5, 8, 10];
const size = 20; // 背包承受重量

接著宣告 knapSack(weight, value, size) 函式,帶入三個參數,並在函式內宣告 bagMatrix ,最後此函式會回傳的是一個二維陣列,詳細記錄求解過程,陣列中元素值最大值者便是總和價值最大的情況。

function knapSack(weight, value, size) {
  let bagMatrix = [];

  return bagMatrix;
}

接著增加兩個 for 迴圈,外層 for 迴圈 w 代表 背包能容納的重量,從0到1, 2,...到背包最大重量,內層 for 迴圈 j 代表 紀錄物品的索引值,另外設定 bagMatrix 的每個元素也都是陣列,形成二維陣列。

function knapSack(weight, value, size) {
  let bagMatrix = [];

  // 外層for迴圈w代表 背包能容納的重量,從0到1, 2,...到背包最大重量
  for (let w = 0; w <= size; w++) {
    bagMatrix[w] = [];
    // 內層for迴圈j代表 紀錄物品的索引值
    for (let j = 0; j < value.length; j++) {
      
    }
  }
  return bagMatrix;
}

在內層 for 完成一些判斷,背包重量為0,肯定不能放任何東西進去,因此該陣列元素為0,背包的容量小於物品 j 的重量,就跟前一個陣列元素值相同,最後比較取物品和不取物品的情況下哪個總價值會最高,將該價值紀錄到陣列內。

function knapSack(weight, value, size) {
  let bagMatrix = [];

  // 外層for迴圈w代表 背包能容納的重量,從0到1, 2,...到背包最大重量
  for (let w = 0; w <= size; w++) {
    bagMatrix[w] = [];
    // 內層for迴圈j代表 紀錄物品的索引值
    for (let j = 0; j < value.length; j++) {
      // 背包重量為0,肯定不能放任何東西進去
      if (w === 0) {
        bagMatrix[w][j] = 0;
        continue;
      }
      // 背包的容量小於物品j的重量
      if (w < weight[j]) {
        bagMatrix[w][j] = bagMatrix[w][j - 1] || 0;
        continue;
      }
      // 這邊紀錄的是取物品和不取物品的情況下,選擇結果較大的值填入陣列內
      bagMatrix[w][j] = Math.max((bagMatrix[w - weight[j]][j - 1] || 0) + value[j], bagMatrix[w][j - 1] || 0);
    }
  }
  return bagMatrix;
}

最後就完成程式了,我們來運行看看,程式執行後印出的樣子:

這次的程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day24-knapsack-problem.js

明天我們將來實作"完美數"的數學問題!


上一篇
Day23-搜尋法系列(二)-二分搜尋法
下一篇
Day25-解題-Perfect Number 完美數
系列文
使用JavaScript學習資料結構與演算法30

尚未有邦友留言

立即登入留言