d890 - 3.禮物分配(gift)

🔗 前往 ZeroJudge 原題

題目描述

題目要求將 n 個單價在 0 到 k 之間變化的禮品分配給兩位經理，使得兩位經理獲得禮品的總價盡可能接近。輸出兩位經理獲得禮品的總價，較小者在前。

解題思路

這題可以轉換為一個子集合和問題。目標是找到一個禮品子集合，其總和盡可能接近總價的一半。可以使用動態規劃來解決這個問題。b[i] 是一個布林陣列，表示是否可以通過選擇一些禮品來獲得總和為 i 的值。初始化 b[0] 為 true，因為總和為 0 總是可行的（不選擇任何禮品）。然後，對於每個禮品 a[i]，從 total - a[i] 到 0 迭代，如果 b[j] 為 true，則 b[j + a[i]] 也為 true。最後，從 total 到 0 迭代 b 陣列，找到第一個 true 值，這表示可以獲得的總和最接近 total 的一半。然後，計算另一位經理的總和，並輸出兩個總和，較小者在前。

複雜度分析

• 時間複雜度: O(n * total)，其中 n 是禮品數量，total 是所有禮品總價。
• 空間複雜度: O(total)，用於儲存動態規劃陣列 b。

程式碼

#include <iostream>
using namespace std;
int main(){
	int n,k,total=0,sum;
	cin >> n >> k;
	int a[n];
	for(int i=0;i<n;++i){
		cin >> a[i];
		total+=a[i];
	}
	sum=total;
	total/=2;
	int b[total+1]={0};
	for(int i=0;i<n;++i){
		for(int j=total-a[i];j>=0;--j){
			if(b[j]||j==0){
				b[j+a[i]]=1;
			}
		}
	}
	if(n==1){
		cout << "0 " << a[0];
	}
	for(int i=total;i>=0;--i){
		if(b[i]){
			cout << i << " " << sum-i;
			break;
		}
	}
}