【題解】Zerojudge b184 - 5. 裝貨櫃問題

題目連結

題目大意

給定 $n$ 個物品的空間 $a_i$ 和價值 $b_i$，問總空間不超過 $100$ 的情況下可以湊出的最高價值為多少？

題解

本題是經典的 01 背包問題，可以透過動態規劃 (Dynamic Programming) 解決。我們定義 $dp[i][j]$ 為前 $i$ 個物品使用 $j$ 空間可以湊出的最高價值。可以發現 $dp[i]$ 的轉移都會從 $dp[i - 1]$ 來，因此可以用滾動式 dp 解決。又因為使用 $j$ 的空間的最高價值也要跟 $j - 1$ 的取 $\max$，因此我們可以反過來做，這樣就只需要一個陣列，不需要滾動。實作的細節請參考 code。

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	while(cin >> n) {
		vector<int> a(n), b(n);
		for(int i = 0; i < n; i++) {
			cin >> a[i] >> b[i];
		}
		vector<int> dp(101);
		for(int i = 0; i < n; i++) {
			for(int j = 100; j >= a[i]; j--) {
				dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
			}
		}
		cout << dp[100] << "\n";
	}
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge b184 - 5. 裝貨櫃問題