UVa 10154 : Weights and Measures

Posted on | In |  
Symbols : 1.9k 字

本題就是著名的烏龜塔題目 :
有 N 隻烏龜，第 i 隻重 Wi 克且有 Si 的力量，代表他可以負載 Si - Wi 的重量在背上
求由這 N 隻烏龜可以疊出的最大高度

測資
Input :

300 1000
1000 1200
200 600
100 101

Output :

3


解法一 : 動態規劃 O( N2)

看著這個題目敘述想一下，發現跟 01 背包問題很像，就來分析一下

  • 有 N 個貨物 <===> 有 N 個烏龜
  • 價值 Vk <===> 重 Wi
  • 重量 Wk <===> 有 Si 的力量
  • 最大容量為 V <===> 最大高度為 H

真的蠻相似的，再從想法上來看
01 背包是取與不取的問題，而烏龜塔也是
所以我們應該可以使用 01 背包問題的概念去解烏龜塔
只是烏龜塔多了一個條件限制 : 底層的烏龜要能夠負荷上面烏龜們的重量
因此我們選擇 suboptimal solution 時，就要去多檢查這項條件

我們還有一項要考慮的問題，那就是 :

那由下往上蓋烏龜塔，還是由上往下蓋呢?

  1. 由下往上蓋
    思考一下這個過程，選了一隻力量夠大的烏龜當最下層，再選第二隻烏龜當第二層，然後檢查一下第一隻撐不撐得住，接下來再挑第三隻烏龜當地三層，同樣地再去檢查一下第一隻烏龜和第二隻烏龜會部會腿軟，挑了第 k 層烏龜後，要去檢查第 1 ~ k - 1 的是否能夠撐住各自的上層重量總和 ……
    呼~~感覺很麻煩呀~
  2. 由上往下蓋
    選一隻比較輕的烏龜當最上層，再選第二隻烏龜當第二層，檢查一下能不能隻撐得住第一隻烏龜，再挑第三隻烏龜出來，同樣地檢查能不能夠撐住上面烏龜重量的總和，挑了第 k 層烏龜，要去檢查此烏龜能不能撐住上面所有的重量 ……
    恩好像比較簡單了

結論 : 由上往下蓋

此外，從剛剛的思考過程我們可以發現，越下層的烏龜需要的力量也越大，越上層的似乎越輕越好，那我們可以利用對烏龜排序來方便我們之後程式的進行，現在又面臨到一個問題了 :

要依照力量排序呢，還是要依照重量排序呢?

舉個例子來看看，我們先用重量排序 :

編號 1 2 3 4
重量 10 20 20 140
力量 60 20 40 150

因為我們是從上往下蓋，所以越上面要越輕，因此我們要從編號 1 開始取
最多可以疊到 2 層 ( 上到下 : 2 –> 4 )

但是，若我們改用力量編號 :

編號 1 2 3 4
重量 20 20 10 140
力量 20 40 60 150

發現最多可以疊到 3 層 ( 上到下 : 1 –> 2 –> 3 )

因此可以知道用重量排序是不對的

那麼用力量排序呢?

Proof :

假設有一組正確答案高度為 m，由上到下所有重量與力量如下 :

重量 W1、W2 … Wm-1、Wm
力量 S1、S2 … Sm-1、Sm

考慮其中有一層 k，依照題意，他能夠支撐住自己與所有上層烏龜的重量 :

Sk >= W1 + W2 + … + Wk-1 + Wk = Sumk
(令 1 ~ k 層的重量為 Sumk )

假設他上一層 k-1 的力量比 k 大，也就是

Sk-1 > Sk

得到 :

Sk-1 > Sk >= Sumk

若我們將第 k-1 層和第 k 層交換，也就是從原本的順序 :

1、2 … k-1 、 k … m

變成下面的順序 :

1、2 … k 、 k-1 … m

烏龜 k 現在需要承受的重量為 Sumk - Wk-1，而烏龜 k-1 需要承受 Sumk
由於烏龜 k 承受的重量減少了，所以可以承受住，又 Sk-1 > Sk >= Sumk
烏龜 k - 1 也可以承受得住此重量，所以我們就算對調這 2 層的烏龜也不會有任何問題，他們都可以抬的動上面的同胞們

因此，每當有相鄰的上層力量比下層大時，把這 2 層對調後一定不會有問題
反覆執行此動作後，我們必然可以將順序調整成烏龜塔由上到下的力量是越來越大的

所以我們用力量排序後在用 DP 去計算得出的答案就會是正確的

證明完畢

這樣我們就可以建構出轉移方程式 :
dp[i][k] = min{ dp[i-1][k] , dp[i][k - 1] + Wi }
其中，dp[i][k - 1] + Wi必須要<= Si 才可以才用
dp[i][k] 的意思是從前 i 隻烏龜中，能夠由上往下建構出 k 層塔的最小重量，若不能的話，狀態則為 Invalid

解法一程式碼

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

class Solution
{
public:
	Solution()
	{
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
	}

	int calculate(vector<pair<int, int>> &data)
	{
		const int INF = 100000000;

		sort(data.begin(), data.end(), [](const pair<int, int> &lhs, const pair<int, int> &rhs) 
		{
			if (lhs.second < rhs.second)
				return true;
			else if (lhs.second == rhs.second)
				return lhs.first < rhs.first;

			return false;
		});

		vector<int> dp(data.size() + 1, INF);

		dp[0] = 0;

		int i, k;

		for (i = 0; i < data.size(); ++i)
			for (k = dp.size() - 1; k >= 1; --k)
			{
				if (dp[k - 1] + data[i].first <= data[i].second)
					dp[k] = min(dp[k], dp[k - 1] + data[i].first);
			}

		for (i = 1; i < dp.size(); ++i)
			if (dp[i] == INF)
				break;

		return i - 1;
	}
};

int main(void)
{
	Solution s;

	vector<pair<int, int>> data;

	data.reserve(5607);

	int w, l;

	while (cin >> w)
	{
		cin >> l;

		data.emplace_back(w, l);
	}

	auto ans = s.calculate(data);

	cout << ans << endl;


	return 0;
}


解法二 : Moore-Hodgson’s Algorithm O( NlogN )

可以先參考這篇了解一下 Moore-Hodgson’s Algorithm

我們再把問題轉換一下

  • N 隻烏龜 <==> N 個 Job
  • 重量 Wi <==> 耗時 Pk
  • 力量 Si <==> Due Di
  • 最高疊 H 層 <==> 最多有 M 個工作可以及時完成 ( 最少工作不能夠被完成的Schedule )

咦????!!!! 一模模一樣樣耶!!!!
OK 那我們就直接用啦~


演算法

  1. 先依照力量將烏龜排序
  2. 遍歷烏龜們 T，將 T[i] 加入到 priority queue 中
  3. 將目前 total_sum 加上 T[i] 的重量
  4. 檢查此烏龜是否可以負荷上層與本身的重量 ( total_sum 是否大於 S[i] )
  5. 若超重，則從 priority queue 中去除最大者，將 total_sum 扣掉他。
  6. 重複步驟 2，直到遍歷完烏龜們
  7. 輸出 : 最後在 T 中尋找到最大的 k 值且 T[k] 是合法狀態，k 即為最大層數

不過因為我們不需要輸出最後堆疊的結果，只需要知道最高層數就好
所以我們就可以簡化一下程式碼，Priority Queue 中只要記錄重量就好，也不需要去紀錄被丟棄的烏龜編號

解法二程式碼

大部分都跟上面的程式碼一樣，只要把 calculate() 函式部分換掉就可以了

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
int calculate(vector<pair<int, int>> &data)
{
	sort(data.begin(), data.end(), [](const pair<int, int> &lhs, const pair<int, int> &rhs)
	{
		if (lhs.second < rhs.second)
			return true;
		else if (lhs.second == rhs.second)
			return lhs.first < rhs.first;
		else
			return false;
	});

	priority_queue<int> pq;
	int i, sum = 0;

	for (i = 0; i < data.size(); ++i)
	{
		pq.push(data[i].first);

		sum += data[i].first;

		if (sum > data[i].second)
		{
			sum -= pq.top();
			pq.pop();
		}
	}

	return pq.size();
}


UVa 真實測資

以下我偷渡出來的 UVa 測資和我的程式 run 的解答，請低調享用

  1. UVa 10154 Test Data
  2. My Ans
0%