01背包

發現躺在queue裡好久, 最近有些時間整理完後發出

這是一個進入dynamic programing的經典例子, 但是很長時候我們都是隨意帶過

特別在筆記一下, 有天需要複習可以再回來看看

首先, 我們有n個物品, 每個物品有他們的重量跟價值

weight: [10, 20, 30]
value: [60, 100, 120]

我們只有一個背包, 他只能放50公斤, 那我們要怎麼塞才能讓這個背包價值可以達到最高

如果窮舉的話

w:[10],           v: 60
w:[20],           v: 100
w:[30],           v: 120
w:[10, 20],       v: 160
w:[10, 30],       v: 180
w:[20, 30],       v: 220
w:[10, 20, 30]    v: X (weight > 50)

可以看到最大就是放20, 30, 整個包包的價值到220

那這邊針對這樣的Case, 我們可以用DFS去解, 可以決定是否要不要這個物品即可

#include <iostream>
#include <vector>
using namespace std;
void dfs(const vector<int> &weights, const vector<int> &values, int W,
         int start, int cur_weight, int cur_value, int &res) {
    if (start >= weights.size()) {
        return;
    }
for (int i = start; i < weights.size(); i++) {
        cur_weight += weights[i];
        cur_value += values[i];
        if (cur_weight <= W)
            res = max(res, cur_value);
        dfs(weights, values, W, i + 1, cur_weight, cur_value, res);
        cur_weight -= weights[i];
        cur_value -= values[i];
    }
}
int knapsack(const vector<int> &weights, const vector<int> &values, int W) {
    int res = 0;
    dfs(weights, values, W, 0, 0, 0, res);
    return res;
}
int main() {
    vector<int> values{60, 10, 100, 120};
    vector<int> weights{10, 15, 20, 30};
    int maxW = 50;
    cout << knapsack(weights, values, 50) << "\n";
    return 0;
}

這樣的時間複雜度是O(2^n)

有沒有更好地做法呢？

接著就是動態規劃

我們建立一個表, 這個表的col表示最大的weight量

row表示可以用的item數目

假設 dp[2][5] , 表示物品只能用0, 1, 2的情況下, 背包空間為5的最大價值

整個01背包的過程強調是在選與不選

我們可以寫下一個方程式說明

dp[i][w]=max(dp[i - 1][w], dp[i - 1][w - wi] + v[i])
dp[i - 1][w]代表不選, 我直接拿上一個item的最大值即可
dp[i - 1][w - wi] + v[i] 代表要選, 所以我們找w - wi的最大值, 再加上當前這個物品的價值

當然, 如果wi > w, 那一定不能選, 因為背包就爆掉了

#include <iostream>
#include <vector>
using namespace std;
int knapsack(const vector<int> &weights, const vector<int> &values, int W) {
  int r = values.size();
  vector<vector<int>> dp(r, vector<int>(W + 1, 0));
for (int i = 0; i < r; i++) {
    for (int j = 1; j <= W; j++) {
      if (i == 0) {
        dp[i][j] = weights[i] > j ? 0 : weights[i];
        continue;
      }
      if (weights[i] > j) {
        dp[i][j] = dp[i - 1][j];
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
      }
    }
  }
return dp[r - 1][W];
}
int main() {
  vector<int> values{60, 10, 100, 120};
  vector<int> weights{10, 15, 20, 30};
  int maxW = 50;
  cout << knapsack(weights, values, 50) << "\n";
return 0;
}