❀ 題目傳送門 ❀

https://atcoder.jp/contests/dp/tasks/dp_e

❀ 解題小技巧 ❀

複雜度

這題跟上一題超像ㄉ，唯一差異就是W跟v範圍。我看了超多遍w
可能有人會想：哼，還不是一樣，直接貼上一題過來就好啦，真菜。不是我
但簡單算一下複雜度

  • D - Knapsack 1

    1 ≤ N ≤ 100
    1 ≤ W ≤ 10^5
    其中，程式碼包含一個 N 包 W 的迴圈（整串程式碼跑最久的地方），
    因此時間複雜度為O(NW)，執行次數則為：N x W => 100 x 10^5 => 10^7。
    而一秒鐘複雜度在 10^7~`10^8 以內是安全的。 而這題是兩秒鐘，程式複雜度10^7，估算時間 => 10^7/10^8` < 2，
    安全~~

  • E - Knapsack 2

    1 ≤ N ≤ 100
    1 ≤ W ≤ 10^9
    若寫法跟上題一樣，時間複雜度為O(NW)，執行次數則為：N x W => 100 x 10^9 => 10^11。
    估算時間 => 10^11/10^8 > 2，爆掉啦！！

解決方法

為此，不能再用同一個寫法了。
稍微改一下核心觀念。

核心觀念

一樣要先有兩個陣列分別儲存「物品價值」跟「物品重量」（下面分別為 v 跟 w）
再來就是 dp 陣列，其中 dp[i] 的意思為背包限重為i時，所能拿的最大價值~
改成 => 其中 dp[i] 的意思為當前價值為i時，所需最小重量。

轉移式

讓我們來看看轉移式：
dp[j] = min(dp[j], dp[j-v[i]] + w[i]);
沒錯，長的超像的，那這邊的意思是：
不拿就有dp[j]價值的重量，或者dp[j-v[i]]拿了v[i]才有dp[j]價值，比dp[j-v[i]]多拿了w[i]重量，
看哪一個小。
由於要比較誰比較小，因此 memset 記得用0x3f（極大的值）。
最後把dp[0]設為 0（當前價值為0時，所需最小重量0），不然就變每個數字都超大（dp[j]、dp[j-v[i]] + w[i];都是極大值）

❀ 參考程式碼 ❀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>

#define burst ios::sync_with_stdio(0); cin.tie(0);
#define int long long

using namespace std;

int w[105], v[105];
int dp[100005]; //當前價值最小重量

signed main(){
  burst
  int N, W;
  cin >> N >> W;
  memset(dp, 0x3f, sizeof(dp));
  for(int i = 0; i < N; i++){
    cin >> w[i] >> v[i];
  }
  dp[0] = 0;
  for(int i = 0; i < N; i++){
    for(int j = 100000; j >= v[i]; j--){
      dp[j] = min(dp[j], dp[j-v[i]] + w[i]);
    }
  }
  for(int i = 100000; i >= 0; i--){
    if (dp[i] <= W) {
      cout << i; 
      break;
    }
  }
  return 0;
}