不知不覺開賽也來到第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

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