d390 - 00562 - Dividing coins

🔗 前往 ZeroJudge 原題

題目描述

題目要求將一組硬幣分成兩堆，使得兩堆硬幣面值的差最小。輸入包含多組測試案例，每組案例包含硬幣的數量和每個硬幣的面值。

解題思路

這題的核心是將硬幣分成兩堆，使得兩堆的總和盡可能接近。這可以轉化為一個子集和問題：找到一個子集，其總和盡可能接近總和的一半。

使用動態規劃 (Dynamic Programming) 來解決這個問題。dp[i] 表示是否能用給定的硬幣組成總和為 i 的子集。初始化 dp[0] 為 true，因為總和為 0 總是可行的（不選任何硬幣）。然後，遍歷每個硬幣，對於每個硬幣 a[i]，從 dps 到 0 遍歷 dp 陣列，如果 dp[j] 為 true，則 dp[j + a[i]] 也為 true。

在遍歷完所有硬幣後，從 dps 到 0 遍歷 dp 陣列，找到第一個 dp[k] 為 true 的 k 值。那麼，最佳分割的差值就是 abs(sum - 2 * k)。

複雜度分析

• 時間複雜度: O(n * dps)，其中 n 是硬幣的數量，dps 是總和的一半。
• 空間複雜度: O(dps)，用於儲存 dp 陣列。

程式碼

#include <iostream>
using namespace std;
int main(){
	int t,n;
	cin >> t;
	while(t--){
		cin >> n;
		int a[n],sum=0;
		for(int i=0;i<n;++i){
			cin >> a[i];
			sum+=a[i];
		} 
		int dps=(sum>>1),min=sum;
		bool dp[dps+1]={1};
		for(int i=0;i<n;++i){
			for(int j=dps;j>=0;--j)
				if(dp[j]==1&&j+a[i]<=dps)
					dp[j+a[i]]=1;
			if(dp[dps]==1)break;		
		}
		for(int k=dps;k>=0;--k){
			if(dp[k]==1){
				cout << abs(sum-2*k) << "\n";
				break;
			}
		}
	}
}