UVa10163 - Storage Keepers (Knapsack Problem)

UVa
字數統計： 1.6k   |   閱讀時間≈ 6分鐘
  1. 題目大意：
  2. 分析：
  3. 背包問題：安全值最高
  4. 背包問題：01 PROBLEM、報酬最低
  5. 參考連結
  6. 心得
  7. 題目程式碼
  8. 用紙筆去模擬 Knapsack Problem

題目大意：

有 X 的倉庫需要有人看守，每個人可以看守多個倉庫，但一個倉庫只能被一人看守，看守的規定如下：
每位看守人員的能力值與報酬相同
如果要讓一看守人員看多個倉庫則其能力值會依照此公式下降 倉庫安全值=看守人員能力值/倉庫數量，有小數點時取整數。
目標是要讓我們花費在看守人員的報酬最低並讓倉庫的安全值最高。

分析：

這題是變化背包問題，不懂背包問題的觀眾可以看一下此連結，不愧是台大的教學材料，質量好到一個極致阿。要是我高中有找點翻到這個資料我一定可以學得更快！，可惜現在的我已經學會了QAQ，想到過去學動態規劃就覺得好辛苦呀..orz。

不過這題必須要用兩個 DP 來解決…，太棒了！這還是我第一次遇到要用兩個 DP 問題去解決題目，我原本一開始以為用一個背包問題去記錄現在的最大安全就好，但沒有考慮到有可能相同的最大安全可能會有不同種的成本，老了，真的老人。已經不是那個刷題大師了。ಥ⌣ಥ

這題要用到兩個 DP，分別是尋找報酬最低與安全值最高。

背包問題：安全值最高

這裡其實應該是一個普通的背包問題，但有一個重點要考慮的是公式 倉庫安全值=看守人員能力值 倉庫數量，所以這裡需要用到 min(dp[j-k] , val[i] / k )來確保有符合公式的條件。

而這段 min 程式碼是怎麼意思呢？分析一下吧！

  • dp[j-k]
    如果前面沒有的倉庫還沒有還沒有被人看守(沒有被看守設值為 0)，於是用這個去判定倉庫有沒有被人看守，如果沒有會因為 min 的關係把現在這個倉庫也先設定成無人看守。
  • val[i] / k
    配合公式讓一個看守人員去管理多個倉庫
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int max_safe(){
    for(int i = 0 ; i < N ; i++) //init
        dp[i] = 0 ;
    dp[0] = INF ;

    for(int i = 0 ; i < m ; i++){ //worker
        for(int j = n ; j > 0 ; j--){ //storage
            for(int k = 1 ; k <= j && val[i] >= k ; k++){ //看守幾個倉庫
            // val[i] >= k 不讓公式的值小於 1
                dp[j] = max(dp[j] , min(dp[j-k] , val[i] / k ));
            }
        }
    }
    return dp[n] ;
}

背包問題：01 PROBLEM、報酬最低

當我們已經有了安全值最高後接下來就要找出報酬最低的數值是多少了，這就是標準的 01 背包問題，我們要怎麼樣選擇工人才能達到報酬率最低。配合上一維陣列壓縮即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int min_cost(){
    if(cost==0) return 0 ; //由於安全性為 0、題目說明工人成本等於安全性，於是安全性為 0 成本也為 0
    for(int i = 0 ; i <= n ; i++) //init
        dp[i] = INF ;
    dp[0] = 0 ;

    for(int i = 0 ; i < m ; i++){
        for(int j = n ; j > 0 ; j--){
            for(int k = min(j , val[i] / cost ) ; k > 0 ; k--){
                dp[j] = min(dp[j] , dp[j-k] + val[i]);
                //debug
                //cout << j << ' ' << dp[j] << ' ' << dp[j-k] + val[i] << '\n' ;
            }

        }
    }
    return dp[n] ;
}

參考連結

uva 10163 - Storage Keepers(01背包）

心得

這題背包問題其實難倒了我了qqq，我一開始寫真的沒有把它想得太深，誤把它當作背包問題的水題帶過(害自己花了 20 min 在思考我怎麼沒有寫對)，下次要能夠多想一點啊！剛好今天也刷了一個經驗值可以讓我在變更優秀些，知道更多知識。也謝謝網路上的大神們分享程式碼讓我可以學習，今天也從JeraKrs學習到了一些比我更棒的命名規則，讓我的腦袋瓜有了更多知識，也謝謝學弟(承恩)給我這題讓我磨練，讓我可以把我的動態規劃知識複習一下，已經好久沒有練習動態規劃，都在寫字串演算法，嗚嗚。

題目程式碼

其實就是沒有附上說明的程式碼，我也花了兩個小時撰寫文章，看得懂跟說得出來真的是兩回事，也許還有人覺得我說的很差，不過我已經盡力解釋。希望可以幫助到各位。

也希望大家想要學習的知識都可以快速學習而成，不要因為自身的環境不足而學習不到。

於是這裡就補述一些題目給的資料範圍限制與標頭檔了。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define N 110
#define M 40
#define INF 1 << 30
using namespace std;
int n , m , dp[N] , val[N] , cost ;

int max_safe(){
    for(int i = 0 ; i < N ; i++)
        dp[i] = 0 ;
    dp[0] = INF ;

    for(int i = 0 ; i < m ; i++){
        for(int j = n ; j > 0 ; j--){
            for(int k = 1 ; k <= j && val[i] >= k ; k++){
                dp[j] = max(dp[j] , min(dp[j-k] , val[i] / k ));
            }
        }
    }
    return dp[n] ;
}

int min_cost(){
    if(cost==0) return 0 ;
    for(int i = 0 ; i <= n ; i++)
        dp[i] = INF ;
    dp[0] = 0 ;

    for(int i = 0 ; i < m ; i++){
        for(int j = n ; j > 0 ; j--){
            for(int k = min(j , val[i] / cost ) ; k > 0 ; k--){
                dp[j] = min(dp[j] , dp[j-k] + val[i]);
                //debug
                //cout << j << ' ' << dp[j] << ' ' << dp[j-k] + val[i] << '\n' ;
            }

        }
    }
    return dp[n] ;
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
#endif // LOCAL
    while(cin >> n >> m && (n || m) ){
        for(int i = 0 ; i < m ; i++)
            cin >> val[i] ;
        cost = max_safe() ;
        cout << cost << ' ' << min_cost() << '\n' ;

    }

    return 0;
}

用紙筆去模擬 Knapsack Problem

因為只是自己在思考過程中隨手做的筆記，覺得不是對讀者這麼有幫助，因此放在文章最下面。

有時候用想或用看的可能不太能夠懂這演算法，那就用寫的吧！這是大衛我自己解這題動態規劃的手稿，如果我文字沒有幫助的話可以考慮看看我的手稿來釐清觀念XD，希望可以幫助到你。


  • 版權聲明： 本部落格所有文章除有特別聲明外，均採用 Apache License 2.0 許可協議。轉載請註明出處！
  • © 2020-2024 John Doe
  • Powered by Hexo Theme Ayer
  • PV:317329 UV:220348