b184 - 5. 裝貨櫃問題

🔗 前往 ZeroJudge 原題

題目描述

題目描述一個經典的 0/1 背包問題。給定多個物品，每個物品有體積和利潤，以及一個容量限制的貨櫃。目標是選擇一些物品放入貨櫃，使得總體積不超過貨櫃容量，且總利潤最大。

解題思路

此題採用動態規劃 (Dynamic Programming) 的方法解決。a[i] 代表體積為 i 時的最大利潤。程式遍歷每個物品，對於每個物品，更新 a 陣列，如果將該物品放入貨櫃後利潤更高，則更新對應的 a[i] 值。 核心邏輯是 if(a[i]+v>a[i-w]) a[i-w]=a[i]+v;，表示如果將當前物品放入後，體積為 i-w 的貨櫃的利潤更高，則更新 a[i-w]。最後，遍歷 a 陣列，找到最大利潤。

複雜度分析

• 時間複雜度: O(n * c)，其中 n 是物品數量，c 是貨櫃容量 (100)。因為有兩層迴圈，外層迴圈遍歷物品，內層迴圈遍歷貨櫃容量。
• 空間複雜度: O(c)，其中 c 是貨櫃容量 (100)。因為使用了一個大小為 101 的 a 陣列來儲存中間結果。

程式碼

#include <iostream>
using namespace std;
int a[101]={0};
int main(){
	int b;
	while(cin >> b){
		int w,v,max=0;
		for(int i=0;i<101;i++)
			a[i]=0;
		while(b--){
			cin >> w >> v;
			for(int i=0;i<=100;i++){
				if(a[i]!=0&&i-w>=0||i==100){
					if(a[i]+v>a[i-w])
						a[i-w]=a[i]+v;
				}
			}
		}
		for(int i=0;i<101;i++){
			if(a[i]>max)
				max=a[i];
		}
		cout << max << '\n';
	}
}