202409潛力3-天秤Libra

may

天秤 (Libra)
問題敘述
教室裡有N個砝碼，重量分別為W1, W2. …, WN公克。請判斷是否有可能將砝碼分成兩堆，分別放上天秤的兩端後會呈現出平衡的狀態，也就是兩邊的重量相等。 例如：有N = 3個砝碼，(W1, W2, W3) = (1, 2, 3)。我們分別將重量為W1和W2的砝碼分成一堆、重量為W3的砝碼自己一堆，放上天秤的兩端之後會呈現出平衡狀態，因為兩邊的重量都是3公克。

輸出格式
請輸出一個整數，整數0表示所有的分法皆不可能出現平衡的狀態、整數1則表示可能出現平衡的狀態。

評分說明
此題目測資分成兩組，每組測資有多筆測試資料，需答對該組所有測試資料才能獲得該組分數，各組詳細限制如下。
第一組 (40 分)：N ≤ 20。
第二組 (60 分)：無特別限制。`
https://zerojudge.tw/ShowProblem?problemid=o628

may

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. bool canBalance(const vector<int>& weights, int totalWeight) {
   
5.     int n = weights.size();
   
6.     vector<bool> dp(totalWeight / 2 + 1, false); // dp[i] 表示是否能夠湊出重量 i
   
7.     dp[0] = true; // 初始狀態：重量 0 一定可以湊出
   
8. 
   
9.     for (int weight : weights) {
   
10.         for (int j = totalWeight / 2; j >= weight; j--) {
    
11.             dp[j] = dp[j] || dp[j - weight];
    
12.         }
    
13.     }
    
14. 
    
15.     return dp[totalWeight / 2];
    
16. }
    
17. 
    
18. int main() {
    
19.     int N;
    
20.     cin >> N;
    
21. 
    
22.     vector<int> weights(N);
    
23.     for (int i = 0; i < N; i++) {
    
24.         cin >> weights[i];
    
25.     }
    
26. 
    
27.     int totalWeight = accumulate(weights.begin(), weights.end(), 0);
    
28. 
    
29.     // 如果總重量不是偶數，則無法平分
    
30.     if (totalWeight % 2 != 0) {
    
31.         cout << 0 << endl;
    
32.         return 0;
    
33.     }
    
34. 
    
35.     // 判斷是否能平分
    
36.     if (canBalance(weights, totalWeight)) {
    
37.         cout << 1 << endl;
    
38.     } else {
    
39.         cout << 0 << endl;
    
40.     }
    
41. 
    
42.     return 0;
    
43. }

複製代碼

may

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const int N = 10005;
   
4. int a[N], n, m, rec[N];
   
5. bool nu;
   
6. void dfs(int start, int sum, int cnt) {
   
7.         if (sum > m) return;//剪枝
   
8.         if (sum == m) {
   
9.                 //for (int i = 0; i < cnt; i++)
   
10.                         //cout << rec[i] << " ";
    
11.                 nu = true;//記錄是否找到一组解
    
12.                 cout<< 1 <<endl;
    
13.                 return;
    
14.         }
    
15.         for (int i = start; i < n; i++) { //重覆性剪枝
    
16.                 rec[cnt] = a[i];  //記錄當前選的值
    
17.                 //cout<<rec[cnt]<<"#";
    
18.                 dfs(i + 1, sum + a[i], cnt + 1); //對下一個進行搜索
    
19.                 if (nu)
    
20.                         return;
    
21.         }
    
22. }
    
23. int main() {
    
24.         cin >> n ;//n個砝碼
    
25.         for (int i = 0; i < n; i++) {
    
26.                 cin >> a[i];//a 陣列裡放n個砝碼
    
27.                 m +=a[i];//砝碼重量加總
    
28.         }
    
29.         if(m%2==1)//總重量若為奇數,不可能出現平衡的狀態
    
30.             cout<<0;
    
31.         m/=2;//若要天秤平衡,必須找到一個子集合的和正好是加總的一半
    
32.         dfs(0, 0, 0);//start,sum,cnt
    
33.         if (!nu)
    
34.                 cout << 0 << endl;
    
35.         return 0;
    
36. }

複製代碼