Board logo

標題: 202409潛力3-天秤Libra [打印本頁]
作者: may    時間: 2024-10-20 15:57     標題: 202409潛力3-天秤Libra

[attach]20106[/attach]
天秤 (Libra)
問題敘述
教室裡有N個砝碼，重量分別為W1, W2. …, WN公克。請判斷是否有可能將砝碼分成兩堆，分別放上天秤的兩端後會呈現出平衡的狀態，也就是兩邊的重量相等。 例如：有N = 3個砝碼，(W1, W2, W3) = (1, 2, 3)。我們分別將重量為W1和W2的砝碼分成一堆、重量為W3的砝碼自己一堆，放上天秤的兩端之後會呈現出平衡狀態，因為兩邊的重量都是3公克。
[attach]20005[/attach]
輸出格式
請輸出一個整數，整數0表示所有的分法皆不可能出現平衡的狀態、整數1則表示可能出現平衡的狀態。
[attach]20006[/attach]
評分說明
此題目測資分成兩組，每組測資有多筆測試資料，需答對該組所有測試資料才能獲得該組分數，各組詳細限制如下。
第一組 (40 分)：N ≤ 20。
第二組 (60 分)：無特別限制。`
https://zerojudge.tw/ShowProblem?problemid=o628
作者: may    時間: 2024-12-16 22:10

  1. #include<bits/stdc++.h>
  2. using namespace std;

  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 一定可以湊出

  9.     for (int weight : weights) {
  10.         for (int j = totalWeight / 2; j >= weight; j--) {
  11.             dp[j] = dp[j] || dp[j - weight];
  12.         }
  13.     }

  15.     return dp[totalWeight / 2];
  16. }

  18. int main() {
  19.     int N;
  20.     cin >> N;

  22.     vector<int> weights(N);
  23.     for (int i = 0; i < N; i++) {
  24.         cin >> weights[i];
  25.     }

  27.     int totalWeight = accumulate(weights.begin(), weights.end(), 0);

  29.     // 如果總重量不是偶數，則無法平分
  30.     if (totalWeight % 2 != 0) {
  31.         cout << 0 << endl;
  32.         return 0;
  33.     }

  35.     // 判斷是否能平分
  36.     if (canBalance(weights, totalWeight)) {
  37.         cout << 1 << endl;
  38.     } else {
  39.         cout << 0 << endl;
  40.     }

  42.     return 0;
  43. }
複製代碼
作者: may    時間: 2024-12-17 22:22

  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. }
複製代碼




歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://istak.org.tw/seed/) Powered by Discuz! 7.2