f168 - m4a2-分配寶物(Treasure)
題目描述
題目要求判斷給定 N 個寶物，其價值分別為 V1 到 Vn，是否能將這些寶物分配給 Alice、Bob 和 Cindy 三個人，使得每個人獲得的寶物價值總和相等。
解題思路
首先，檢查寶物總價是否能被 3 整除。如果不能，則直接輸出 "NO"。如果能，則目標價值為總價除以 3。
使用深度優先搜尋 (DFS) 嘗試將寶物分配給三個人。u[i] 陣列用於標記寶物是否已被分配，1 表示分配給 Alice，2 表示分配給 Bob。
DFS 的基本思路是：
- 嘗試將寶物分配給 Alice，如果分配後 Alice 的總價值不超過目標價值，則遞迴分配後續寶物。
- 如果 Alice 的分配完成，則嘗試將寶物分配給 Bob，條件與 Alice 相同。
- 如果 Alice 和 Bob 的分配完成，則檢查是否所有寶物都被分配，且 Alice 和 Bob 的總價值都等於目標價值。如果滿足，則找到解，輸出 "YES"。 如果 DFS 遍歷所有可能的分配方案都找不到解，則輸出 "NO"。
複雜度分析
- 時間複雜度: O(3^N)。在最壞情況下，每個寶物都有 3 種分配方式（Alice、Bob 或不分配），因此時間複雜度為指數級。
- 空間複雜度: O(N)。主要用於儲存
a陣列（寶物價值）、u陣列（分配狀態）和遞迴呼叫堆疊。
程式碼
#include <iostream>
using namespace std;
int a[17],n,sum,g,y,u[17];
void dfs(int it,int no,int no2){
if(y)return;
if(no==g&&no2==g){
y=1;
return;
}
else if(no==g){
for(int i=0;i<n;++i){
if(u[i]==0&&a[i]+no2<=g){
u[i]=2;
dfs(i,no,no2+a[i]);
u[i]=0;
}
}
}
else{
for(int i=it+1;i<n;++i){
if(u[i]==0&&a[i]+no<=g){
u[i]=1;
dfs(i,no+a[i],no2);
u[i]=0;
}
}
}
}
int main(){
cin >> n;
for(int i=0;i<n;++i){
cin >> a[i];
sum+=a[i];
}
if(sum%3)
cout << "NO";
else{
g=sum/3;
for(int i=0;i<n;++i){
u[i]=1;
dfs(i,a[i],0);
u[i]=0;
}
if(y)
cout << "YES\n";
else
cout << "NO\n";
}
}