# 演算法作業筆記
# sort compare
會給csv檔案 對每一排的數字去排序
然後比較各個排序的差別
同量級sort O(nlgn)
加入bubble sort O(n^2)
```cpp
#include <chrono>
#include <fstream>
#include <iostream>
#include <sstream>
#define int long long
using namespace std;
using namespace std::chrono;
void bubble_sort(vector<int> &arr) {
for (int i = 0; i < arr.size(); i++) {
for (int j = i + 1; j < arr.size(); j++) {
if (arr[i] > arr[j]) swap(arr[i], arr[j]);
}
}
}
int qsort_partirion(vector<int> &arr, int head, int tail) {
int i = head;
for (int j = head; j < tail; j++) {
if (arr[j] < arr[tail]) {
swap(arr[i], arr[j]);
i++;
}
}
swap(arr[i], arr[tail]);
return i;
}
void quick_sort(vector<int> &arr, int head, int tail) {
if (head < tail) {
int mid = qsort_partirion(arr, head, tail);
quick_sort(arr, head, mid - 1);
quick_sort(arr, mid + 1, tail);
}
}
void heap_merge(vector<int> &arr, int head, int tail) {
int mid = (head + tail) / 2;
int i = 0, j = 0;
vector<int> left(arr.begin() + head, arr.begin() + mid + 1);
vector<int> right(arr.begin() + mid + 1, arr.begin() + tail + 1);
left.push_back(INT_MAX);
right.push_back(INT_MAX);
for (int k = head; k <= tail; k++) {
if (left[i] < right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
}
}
void heap_sort(vector<int> &arr, int head, int tail) {
if (head < tail) {
int mid = (head + tail) / 2;
heap_sort(arr, head, mid);
heap_sort(arr, mid + 1, tail);
heap_merge(arr, head, tail);
}
}
int cal_sort_time(vector<int> &arr, int round) {
auto start = high_resolution_clock::now(); // 計時開始
if (round == 0) {
bubble_sort(arr);
} else if (round == 1) {
quick_sort(arr, 0, arr.size() - 1);
} else if (round == 2) {
sort(arr.begin(), arr.end());
} else if (round == 3) {
heap_sort(arr, 0, arr.size() - 1);
}
auto end = high_resolution_clock::now(); // 計時結束
auto durationStd = duration_cast<nanoseconds>(end - start); // 計算耗時
return durationStd.count();
}
signed main() {
int avg = 0;
string line;
fstream file("data.csv");
if (!file) {
cerr << "無法開啟檔案" << endl;
}
ios_base::sync_with_stdio(false);
cin.tie(0);
for (int i = 0; i < 4; i++) {
int cnt = 1;
file.clear();
file.seekg(0);
switch (i) {
case 0:
cout << "氣泡排序" << endl;
break;
case 1:
cout << "快速排序" << endl;
break;
case 2:
cout << "內建排序" << endl;
break;
case 3:
cout << "推積排序" << endl;
break;
default:
break;
}
while (getline(file, line)) {
if (!line.empty() && line.back() == '\r') {
line.pop_back();
}
stringstream s(line);
string tmp;
vector<int> arr;
while (getline(s, tmp, ',')) {
arr.push_back(stoi(tmp));
}
// 2次取平均
avg = 0;
for (int j = 0; j < 2; j++) {
vector<int> tmp_arr = arr;
avg += cal_sort_time(tmp_arr, i);
}
avg /= 2;
cout << "第" << cnt << "筆資料：" << "花費時間 " << cal_sort_time(arr, i) << " 10^-9秒" << endl;
//cout << cal_sort_time(arr, i) << endl;
cnt++;
}
cnt = 0;
}
}
```
# strassen algorithm
:::spoiler 題目敘述
# Strassen 演算法（矩陣乘法）
## 描述
請利用 **Strassen algorithm** 計算兩個矩陣 A 和 B 的乘積，並輸出結果矩陣 A × B。
---
## 輸入格式（Input Description）
輸入為一行，包含 `a b c d` 以及矩陣 `A` 和 `B` 的所有數據，數字之間以空格分隔：
- `a`：矩陣 A 的行數
- `b`：矩陣 A 的列數
- `c`：矩陣 B 的行數
- `d`：矩陣 B 的列數
- 接下來 `a × b` 個數字為矩陣 A 的內容，**按行優先順序（row-major order）**排列。
- 接下來 `c × d` 個數字為矩陣 B 的內容，也按行優先順序排列。
> 注意：矩陣 A 的列數 `b` 必須等於矩陣 B 的行數 `c`，否則無法進行矩陣乘法。
---
## 行優先順序說明（Row-major Order）
矩陣 A（2 × 3）
```
1 2 3
4 5 6
```
展開為：`1 2 3 4 5 6`
---
## 輸出格式（Output Description）
輸出為一行，包含結果矩陣 A × B 的所有元素，**按行優先順序**排列，數字之間以空格分隔。
---
## 輸入範例與輸出範例
### 範例 1
**輸入：**
```
2 3 3 1
28893 23045 18093 11540 6361 25604
19464 7688 8283
```
**輸出：**
```
889407631 485595860
```
---
### 範例 2
**輸入：**
```
2 3 3 2
27723 6064 284 4708 19363 19276
26863 1324 15002 696 15217 9524
```
**輸出：**
```
840016705 43630612 710277622 203294664
```
---
### 範例 3
**輸入：**
```
4 4 4 4
15944 20701 6920 17918 269 10820 17870 7428 23752 16924 3906 10901 16834 15284 6284 403
10474 15240 17808 14495 6031 14444 7578 16022 1088 2888 27827 177 16995 17626 17570 7842
```
**輸出：**
```
603890557 877799432 948185030 704517498 213754346 342918128 714562762 238670561 540359315 809852290 851448520 701618572 282183097 502563726 597547602 493161672
```
:::
```cpp
#include <iostream>
#include <vector>
#include <bit>
#define int long long
using namespace std;
int nextPowerOf2(int n) {
if (n <= 0) return 1;
n--;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n |= n >> 32;
return n + 1;
}
vector<vector<int>> add(vector<vector<int>> matrix1, vector<vector<int>> matrix2) {
int size = matrix1.size();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
matrix1[i][j] = matrix1[i][j] + matrix2[i][j];
}
}
return matrix1;
}
vector<vector<int>> sub(vector<vector<int>> matrix1, vector<vector<int>> matrix2) {
int size = matrix1.size();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
matrix1[i][j] = matrix1[i][j] - matrix2[i][j];
}
}
return matrix1;
}
vector<vector<int>> matrix_multiply(vector<vector<int>> matrix1, vector<vector<int>> matrix2) {
int size = matrix1.size();
if (size <= 0) {
return vector<vector<int>>();
}
if (size < 10) {
vector<vector<int>> result(size, vector<int>(size, 0));
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
for (int k = 0; k < size; k++) {
result[i][j] += matrix1[i][k] * matrix2[k][j];
}
}
}
return result;
}
int new_size = size / 2;
vector<vector<int>> ans(size, vector<int>(size, 0));
vector<vector<int>> a11(new_size, vector<int>(new_size, 0));
vector<vector<int>> a12(new_size, vector<int>(new_size, 0));
vector<vector<int>> a21(new_size, vector<int>(new_size, 0));
vector<vector<int>> a22(new_size, vector<int>(new_size, 0));
vector<vector<int>> b11(new_size, vector<int>(new_size, 0));
vector<vector<int>> b12(new_size, vector<int>(new_size, 0));
vector<vector<int>> b21(new_size, vector<int>(new_size, 0));
vector<vector<int>> b22(new_size, vector<int>(new_size, 0));
for (int i = 0; i < new_size; i++) {
for (int j = 0; j < new_size; j++) {
a11[i][j] = matrix1[i][j];
a12[i][j] = matrix1[i][j + new_size];
a21[i][j] = matrix1[i + new_size][j];
a22[i][j] = matrix1[i + new_size][j + new_size];
b11[i][j] = matrix2[i][j];
b12[i][j] = matrix2[i][j + new_size];
b21[i][j] = matrix2[i + new_size][j];
b22[i][j] = matrix2[i + new_size][j + new_size];
}
}
vector<vector<int>> m1 = matrix_multiply(add(a11, a22), add(b11, b22));
vector<vector<int>> m2 = matrix_multiply(add(a21, a22), b11);
vector<vector<int>> m3 = matrix_multiply(a11, sub(b12, b22));
vector<vector<int>> m4 = matrix_multiply(a22, sub(b21, b11));
vector<vector<int>> m5 = matrix_multiply(add(a11, a12), b22);
vector<vector<int>> m6 = matrix_multiply(sub(a21, a11), add(b11, b12));
vector<vector<int>> m7 = matrix_multiply(sub(a12, a22), add(b21, b22));
vector<vector<int>> c11 = add(sub(add(m1, m4), m5), m7);
vector<vector<int>> c12 = add(m3, m5);
vector<vector<int>> c21 = add(m2, m4);
vector<vector<int>> c22 = add(sub(add(m1, m3), m2), m6);
vector<vector<int>> result(size, vector<int>(size));
for (int i = 0; i < new_size; i++) {
for (int j = 0; j < new_size; j++) {
result[i][j] = c11[i][j];
result[i][j + new_size] = c12[i][j];
result[i + new_size][j] = c21[i][j];
result[i + new_size][j + new_size] = c22[i][j];
}
}
return result;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int a, b, c, d;
int size = 0;
cin >> a >> b >> c >> d;
size = nextPowerOf2(max(a, b, d));
vector<vector<int>> matrix1(size, vector<int>(size, 0));
vector<vector<int>> matrix2(size, vector<int>(size, 0));
for (int i = 0; i < a; i++) {
for (int j = 0; j < b; j++) {
cin >> matrix1[i][j];
}
}
for (int i = 0; i < c; i++) {
for (int j = 0; j < d; j++) {
cin >> matrix2[i][j];
}
}
// matrix1 * matrix2
vector<vector<int>> ans(size, vector<int>(size, 0));
ans = matrix_multiply(matrix1, matrix2);
for (int i = 0; i < a; i++) {
for (int j = 0; j < d; j++) {
cout << ans[i][j] << " ";
}
}
return 0;
}
```
# Traveling Salesman Problem
:::spoiler 題目敘述
# 旅行推銷員問題（TSP）
## 描述
給定一個有向圖，頂點代表城市，邊代表從城市 `i` 到城市 `j` 的路徑，其**權重表示距離**。距離矩陣中：
- 每個數字代表從城市 `i` 到城市 `j` 的距離。
- 若某一數字為 `-1`，表示從城市 `i` 到城市 `j` **無法直接到達**。
- 對角線上的數值皆為 `0`（城市到自身距離為 0）。
請找出一個巡迴路徑，使得：
1. 選定一個起始城市出發，
2. 走訪所有城市恰好一次，
3. 最後返回起始城市，
4. 每一步行走必須沿著存在的路徑（即距離不為 `-1`）。
在**所有可行的巡迴路徑**中，找出**總距離最短**的那一條。
- 若存在多條總距離相同的最短巡迴路徑，可輸出任一一條；
- 若**不存在任何可行的巡迴路徑**，則輸出 `-1`。
---
## 輸入格式
- 第一行：一個正整數 `N`（`N ≥ 2`），代表城市數量。
- 接下來 `N` 行：每行包含 `N` 個整數，表示從城市 `i` 到城市 `j` 的距離。
---
## 輸出格式
- 若存在可行的巡迴路徑，輸出一行，依序列出巡迴路徑中經過的城市編號（以**空格分隔**），其中起始城市與終點城市相同。
- 若不存在任何可行巡迴路徑，則輸出 `-1`。
---
## 輸入範例與輸出範例
### 範例 1
**輸入：**
```
6
0 14 12 -1 -1 17
2 0 -1 18 11 19
13 7 0 6 -1 -1
12 -1 4 0 20 3
16 7 1 19 0 9
-1 3 3 4 17 0
```
**輸出：**
```
1 3 4 6 5 2 1
```
---
### 範例 2
**輸入：**
```
7
0 1 -1 9 2 10 -1
16 0 -1 3 -1 14 4
17 2 0 -1 12 -1 20
-1 20 4 0 15 15 2
8 3 2 7 0 11 -1
6 2 12 2 16 0 6
10 11 -1 7 8 17 0
```
**輸出：**
```
1 5 3 2 4 7 6 1
```
---
### 範例 3
**輸入：**
```
8
0 18 20 -1 -1 6 5 13
20 0 -1 15 14 -1 -1 7
-1 6 0 7 14 11 -1 7
11 20 10 0 8 10 -1 10
7 -1 1 8 0 16 -1 -1
15 3 -1 3 13 0 20 -1
19 3 18 -1 11 -1 0 12
4 4 11 12 10 11 -1 0
```
**輸出：**
```
1 7 5 3 4 6 2 8 1
```
:::
```cpp
#include <iostream> // 引入標準輸入輸出函式庫
#include <cmath> // 引入數學函式庫（本程式中未實際使用）
#include <cstring> // 引入 C 字串操作函式庫（未使用）
#include <vector> // 引入動態陣列 vector 類別
using namespace std; // 使用標準命名空間，方便後續使用 cout、vector 等
#define N 5 // 定義城市數量為 5
#define INF 10e7 // 定義無限大的值，代表城市間無連接（用於距離初始化）
#define min(a,b) ((a>b)?b:a) // 定義一個 min 宏，用於取兩數中的最小值
static const int M = 1 << (N-1); // 狀態總數：1<<(N-1)，代表除了起點外其他城市的子集合數量
// 城市之間的距離矩陣，g[i][j] 代表城市 i 到城市 j 的距離
int g[N][N] = {
{0, 3, INF, 8, 9},
{3, 0, 3, 10, 5},
{INF, 3, 0, 4, 3},
{8, 10, 4, 0, 20},
{9, 5, 3, 20, 0}
};
// dp[i][s] 表示從城市 i 出發，走訪集合 s 中的所有城市，最後回到起點的最短距離
int dp[N][M];
// 用來儲存最短路徑的城市順序
vector<int> path;
// 求解 TSP 問題的主函式，使用動態規劃計算 dp 陣列
void TSP(){
// 初始化：當狀態為空（s=0），表示不走訪任何城市，只從 i 回到起點 0
for(int i = 0 ; i < N ; i++){
dp[i][0] = g[i][0]; // 不經過其他點，直接回起點
}
// 計算所有狀態 dp[i][j]
for(int j = 1 ; j < M ; j++){
for(int i = 0 ; i < N ; i++){
dp[i][j] = INF; // 預設為無限大（尚未計算）
// 如果狀態 j 包含節點 i，就跳過，因為不能從 i 出發走訪自己
if(((j >> (i-1)) & 1) == 1){
continue;
}
// 嘗試所有可能的中繼節點 k，從 i 前往 k，並且剩餘狀態為 j ^ (1<<(k-1))
for(int k = 1 ; k < N ; k++){
if(((j >> (k-1)) & 1) == 0){
continue; // 若狀態 j 不包含 k，就跳過
}
// 更新 dp[i][j] 為當前最小值
if(dp[i][j] > g[i][k] + dp[k][j ^ (1<<(k-1))]){
dp[i][j] = g[i][k] + dp[k][j ^ (1<<(k-1))];
}
}
}
}
}
// 檢查除了起點（0）外，其他城市是否都已經訪問
bool isVisited(bool visited[]){
for(int i = 1 ; i < N ; i++){
if(visited[i] == false){
return false;
}
}
return true;
}
// 根據 dp 陣列反推路徑，結果儲存在 path 向量中
void getPath(){
bool visited[N] = {false}; // 訪問標記初始化
int pioneer = 0; // 初始點為 0（起點）
int min = INF; // 記錄目前找到的最小距離
int S = M - 1; // 初始狀態為所有節點都尚未訪問（除了起點）
int temp; // 記錄下一個節點
path.push_back(0); // 起點加入路徑中
// 持續選擇下一個最佳節點直到所有節點都訪問
while(!isVisited(visited)){
for(int i = 1; i < N; i++){
if(!visited[i] && (S & (1 << (i-1))) != 0){ // 如果還沒訪問且 S 包含節點 i
// 嘗試是否從目前節點 pioneer 到 i 的這條路徑是最短
if(min > g[i][pioneer] + dp[i][S ^ (1 << (i-1))]){
min = g[i][pioneer] + dp[i][S ^ (1 << (i-1))];
temp = i; // 記錄下個最佳節點
}
}
}
pioneer = temp; // 更新目前節點
path.push_back(pioneer); // 加入路徑
visited[pioneer] = true; // 標記已訪問
S = S ^ (1 << (pioneer - 1)); // 從狀態中移除該節點
min = INF; // 重置最小距離
}
}
// 印出路徑
void printPath(){
cout << "最小路径为：";
vector<int>::iterator it = path.begin();
for(it ; it != path.end(); it++){
cout << *it << "--->";
}
cout << 0; // 最後回到起點
}
int main(){
TSP(); // 計算最短路徑距離
cout << "最小值为：" << dp[0][M-1] << endl; // 印出最短距離值
getPath(); // 根據 dp 陣列計算實際最短路徑
printPath(); // 印出路徑順序
return 0;
}
```
# Huffman coding
:::spoiler 題目敘述
# 霍夫曼編碼
## 描述
因為 OJ 平台限制，輸入為 ASCII 文字。
給定一行文字，請依照以下步驟產生霍夫曼編碼，最後把整條位元序列轉成大寫的十六進位字串輸出，不要有空格或換行。
## 步驟
1. **計算頻率**：統計每個字元在文字中出現的次數。
2. **建立最小堆**：每個節點包含「字元／子樹」和它的排序鍵（頻率＋次序）。
- 主要排序鍵：頻率（出現次數）越小越優先。
- 次要排序鍵：若頻率相同，就比較該字元在原文字中第一次出現的位置（越靠前優先）。
3. **合併節點**：
- 每次從最小堆取出兩個最小的節點合併成新節點，並將它放回堆中。
- 新節點的「次序」由左右子節點中優先級高者決定。
4. **產生編碼**：從根節點到每個葉節點，走左邊加 0 、走右邊加 1 ，得到每個字元的霍夫曼碼。
5. **輸出結果**：把原文字逐字元替換成對應的二進位編碼，串成一長條，再轉成大寫十六進位字串。
---
## 範例一
**原始文字統計：**
```text
{'黑': 7, '化': 7, '肥': 7, '揮': 7, '發': 14, '會': 3, '灰': 7, '，': 4, '。': 1, '到': 1, '底': 1, '是': 2, '還': 1, '？': 1}
```
**排序結果：**
```text
{'。': 1, '到': 1, '底': 1, '還': 1, '？': 1, '是': 2, '會': 3, '，': 4, '黑': 7, '化': 7, '肥': 7, '揮': 7, '灰': 7, '發': 14}
```
**霍夫曼編碼結果：**
```text
'化': 000
'肥': 001
'揮': 010
'灰': 011
'發': 10
'，': 1100
'底': 110100
'還': 110101
'是': 11011
'會': 11100
'？': 111010
'。': 1110110
'到': 1110111
'黑': 1111
```
**重組後：**
```text
黑化肥揮發會... → 1111 000 001 010 10 11100 ...
```
**十六進位輸出：**
```text
F055C...
```
## 輸入與輸出說明
### 輸入
一行任意文字，可能包含中文、英文、符號、數字等 UTF-8 常見字元。
### 輸出
轉換後的十六進位編碼字串（大寫字母），不包含任何空格或換行。
## 輸入範例與輸出範例
### 範例 1
**輸入：**
```
黑化肥揮發會發灰黑化肥發灰會揮發，灰化肥揮發會發黑。黑化肥揮發發灰，灰化肥揮發發黑，到底是黑化肥揮發發灰，還是灰化肥揮發發黑？
```
**輸出：**
```
F055C9F833E2B182AE5FDBC154F182ABF3BE9BF0553CD76C155FD0
```
### 範例 2
**輸入：**
```
我最近發明了一種東西，相信可以幫你。手電筒？錯！這一支不是普通的手電筒，這一支是不需要電池的太陽能手電筒！在有光的時候它就會亮！那如果沒有光的時候......絕對不亮！有沒有可能沒有光的時候它也會亮？問得好！關燈。哪~~你拿出另外一支手電筒來照它呢，它就會亮......嘿~~怎麼樣哪？開燈！這個發明還真有創意啊！
```
**輸出：**
```
F0F1F2F5EFCFEFCFDFEABFC0020420620E64AC2F6CFADB85285683992AB3EB45B8B17998A193470E64E9BC5F4CB341FC27AA14AAE717D32CF7777755ACB93DC73804EE717D32CD0B784D6B97B0EB164469CE0DB3778F7EB47323E7E881520FE13BBBBBB05CE850E2355C567B646F5EE3C8C49952FA
```
### 範例 3
**輸入：**
```
See your body into the moonlightEven if I try to cancelAll the pictures into the mind...
```
**輸出：**
```
9D13E902976A2BA77BC8F9B3D3117A38F793B4F37DEAF6FE4A9F23A01681D2A69A7CD9E89D0C148AF...
```
### 範例 4
**輸入：**
```
'[Khp:wvwD
```
**輸出：**
```
CDEF058D
```
:::
```cpp
#include <bits/stdc++.h>
#include <codecvt> // 把 UTF-8 轉成 UTF-32
using namespace std;
/* ---------- 節點定義 ---------- */
struct Node {
char32_t ch; // 葉節點存字元，內部節點可設為 0
long long freq; // 出現次數
int order; // 第一出現的位置（越小越優先）
Node *left, *right;
bool isLeaf;
Node(char32_t c, long long f, int o, bool leaf)
: ch(c), freq(f), order(o), left(nullptr), right(nullptr), isLeaf(leaf) {}
};
/* ---------- 最小堆比較器 ----------
* 1. 次數少優先
* 2. 次數相等時，order 小者優先
*/
struct Cmp {
bool operator()(const Node* a, const Node* b) const {
return (a->freq == b->freq) ? a->order > b->order
: a->freq > b->freq;
}
};
/* ---------- DFS 產生霍夫曼碼 ---------- */
void buildCode(Node* node, const string& cur,
unordered_map<char32_t,string>& code) {
if (!node) return;
if (node->isLeaf) {
code[node->ch] = cur.empty() ? "0" : cur; // 只有一種字元時給 '0'
return;
}
buildCode(node->left , cur + '0', code);
buildCode(node->right, cur + '1', code);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
/* 讀取一整行（UTF-8 文字） */
string raw;
getline(cin, raw);
/* 把 UTF-8 轉成 UTF-32，才能「一個字元」為單位統計頻率 */
wstring_convert<std::codecvt_utf8<char32_t>, char32_t> conv;
u32string txt = conv.from_bytes(raw);
/* ---------- 1. 統計頻率 & 記錄第一次出現順序 ---------- */
unordered_map<char32_t,long long> freq;
unordered_map<char32_t,int> firstPos;
for (size_t i = 0; i < txt.size(); ++i) {
char32_t c = txt[i];
++freq[c];
if (!firstPos.count(c)) firstPos[c] = static_cast<int>(i);
}
/* ---------- 2. 建立最小堆 ---------- */
priority_queue<Node*, vector<Node*>, Cmp> pq;
for (auto& [c, f] : freq) {
pq.push(new Node(c, f, firstPos[c], true));
}
/* ---------- 3. 反覆合併 ---------- */
while (pq.size() > 1) {
Node* a = pq.top(); pq.pop();
Node* b = pq.top(); pq.pop();
int newOrder = (Cmp{}(a,b) ? a->order : b->order); // 較高優先者
Node* parent = new Node(0, a->freq + b->freq, newOrder, false);
parent->left = a;
parent->right = b;
pq.push(parent);
}
Node* root = pq.top(); // 最後剩下一個就是根
/* ---------- 4. 產生每個字元的霍夫曼碼 ---------- */
unordered_map<char32_t,string> code; // 字元 → bit 字串
buildCode(root, "", code);
/* ---------- 5. 把原文轉成 bit 串 ---------- */
string bits;
bits.reserve(txt.size() * 8); // 粗抓容量，省得一直 realloc
for (char32_t c : txt) bits += code[c];
/* 尾端補 0 讓長度變成 4 的倍數，方便轉十六進位 */
while (bits.size() % 4) bits.push_back('0');
/* ---------- bit → HEX ---------- */
string hex;
hex.reserve(bits.size() / 4);
for (size_t i = 0; i < bits.size(); i += 4) {
int val = (bits[i] - '0') * 8 +
(bits[i+1] - '0') * 4 +
(bits[i+2] - '0') * 2 +
(bits[i+3] - '0');
hex.push_back("0123456789ABCDEF"[val]);
}
cout << hex << '\n';
/* ---------- 記得釋放動態節點 (純樸版直接遞迴刪除) ---------- */
function<void(Node*)> clear = [&](Node* n) {
if (!n) return;
clear(n->left);
clear(n->right);
delete n;
};
clear(root);
return 0;
}
```
# sum of subsets
:::spoiler 題目敘述
# 子集合總和（Sum of Subsets）
## 描述
給定一個目標總和 `W`，以及 `n` 個正整數，代表 `n` 個物品的重量 `w₁, w₂, ..., wₙ`。
請找出所有可以讓所選子集合的總和 **恰好等於 W** 的選法。
每種選法以 **長度為 n 的二進位序列** 表示，其中：
- `1` 表示選取該項，
- `0` 表示不選。
然後將每種合法選法視為一個 **二進位整數**，並轉換為 **十進位整數**輸出。
---
## 補充說明
1. 每個子集合的選取方式可用長度為 `n` 的 **二進位字串** 表示：
- 例如長度為 4 的選法 `1101` 表示：選取第 1、2、4 項，不選第 3 項。
2. 將該二進位字串轉為十進位整數作為輸出：
- 例如 `1101（二進位） = 13（十進位）`
3. 請考慮所有 `2ⁿ` 種選法，僅輸出**總和為 `W`** 的選法對應整數。
4. 最終輸出以 **空格分隔**，並 **由小到大排序**。
---
## 輸入格式
一行，共 `n + 1` 個整數：
```
W w₁ w₂ ... wₙ
```
- `W`：目標總和
- `wᵢ`：第 i 個物品重量
- `n`：物品數量
---
## 輸出格式
在同一行中，輸出所有合法子集合（即總和為 `W`）對應的**十進位整數**，以**空格分隔**，**升冪排列**。
---
## 輸入範例與輸出範例
### 範例 1
**輸入：**
```
24 5 4 14 1 6
```
**輸出：**
```
13 30
```
---
### 範例 2
**輸入：**
```
41 6 9 5 11 6 18 1
```
**輸出：**
```
31 78 91
```
---
### 範例 3
**輸入：**
```
13422 4154 5399 4758 1615 9268 7332 6632 7304 9756 7949
```
**輸出：**
```
544
```
---
### 範例 4
**輸入：**
```
356392 52841 30511 1753 46882 51929 2855 54304 16853 40250 43295 32520 51256 35711 34162 30552 7438 50268 558 39822 19127
```
**輸出：**
```
349887 644619 820477 838287 890038
```
:::
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
/* ---------------- 讀取輸入 ---------------- */
vector<long long> w; // 物品重量
long long W; // 目標總和
if (!(cin >> W)) return 0; // 空輸入保險
long long x;
while (cin >> x) w.push_back(x);
int n = static_cast<int>(w.size());
/* ---------------- 列舉所有子集合 ---------------- */
vector<unsigned long long> ans; // 符合條件的 bitmask（十進位）
const unsigned long long total = 1ULL << n; // n ≤ 63 假設
for (unsigned long long mask = 0; mask < total; ++mask) {
long long sum = 0;
for (int i = 0; i < n; ++i)
if (mask & (1ULL << (n - 1 - i))) // 最高位對應 w1
sum += w[i];
if (sum == W) ans.push_back(mask);
}
/* ---------------- 輸出（自然就是升冪） ---------------- */
for (size_t i = 0; i < ans.size(); ++i) {
if (i) cout << ' ';
cout << ans[i];
}
cout << '\n';
return 0;
}
```
# double bag problem
:::spoiler
# 雙重限制背包問題
## 題目描述
小華擁有一個背包，背包有兩個限制：**最大重量** \(W\) 以及 **最大體積** \(V\)。
他面前有 \(n\) 個物品，每個物品各自具有固定的 **重量**、**體積** 與 **價值**，且每件物品最多只能選擇一次。
請你利用 **DFS** 枚舉所有可能的選擇組合，找出在不超過背包限制的前提下，可取得的 **最大總價值**。
---
## 輸入格式
1. 第一行包含三個整數 `W V n`
- `W` — 背包可承受的最大重量
- `V` — 背包可容納的最大體積
- `n` — 物品數量
2. 接下來的 `n` 行，每行包含三個整數 `w v val`
- `w` — 該物品的重量
- `v` — 該物品的體積
- `val` — 該物品的價值
---
## 輸出格式
輸出一行，一個整數，代表在不超過背包限制下能取得的 **最大總價值**。
---
## 範例
### 範例輸入 1
20 30 4
3 5 25
2 3 4
8 4 16
7 2 4
### 範例輸出 1
49
---
### 範例輸入 2
15 25 5
1 1 3
6 2 24
5 3 20
4 5 2
10 6 6
### 範例輸出 2
47
---
### 範例輸入 3
25 35 6
4 5 35
3 3 31
10 1 1
8 3 15
4 6 31
9 7 31
### 範例輸出 3
128
:::
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int W, V, n;
int maxValue = 0;
struct Item {
int weight;
int volume;
int value;
};
vector<Item> items;
void dfs(int index, int currWeight, int currVolume, int currValue) {
if (currWeight > W || currVolume > V) return;
maxValue = max(maxValue, currValue);
if (index == n) return;
dfs(index + 1, currWeight, currVolume, currValue);
dfs(index + 1,
currWeight + items[index].weight,
currVolume + items[index].volume,
currValue + items[index].value);
}
int main() {
cin >> W >> V >> n;
items.resize(n);
for (int i = 0; i < n; ++i) {
cin >> items[i].weight >> items[i].volume >> items[i].value;
}
dfs(0, 0, 0, 0);
cout << maxValue << endl;
return 0;
}
```
# multiple bags problem
::: spoiler
# 多重數量限制背包問題（Bounded Knapsack）
## 題目描述
小明有一個容量為 **\(C\)** 的背包。
他面前有 **\(n\)** 種物品，每種物品皆具備 **重量**、**價值**，且同一種類的物品可以選多件，但至多只能選 **\(K_i\)** 件。
請使用 **Knapsack（動態規劃 / DFS 皆可）**，在不超過背包容量的前提下，求得可取得的 **最大總價值**。
---
## 輸入格式
1. **第一行**：兩個整數 `C n`
- `C` — 背包容量
- `n` — 物品種類數
2. **接下來的 n 行**：每行三個整數 `w v k`
- `w` — 該物品的重量 \(w_i\)
- `v` — 該物品的價值 \(v_i\)
- `k` — 該物品可選的最大件數 \(K_i\)
---
## 輸出格式
輸出一行，一個整數，代表在容量限制下能取得的 **最大總價值**。
---
## 範例
### 範例輸入 1
30 4
1 5 1
4 8 2
4 4 1
4 1 2
### 範例輸出 1
27
---
### 範例輸入 2
25 5
1 6 2
6 5 3
5 4 1
5 3 4
6 7 3
### 範例輸出 2
37
---
### 範例輸入 3
35 6
5 3 3
5 8 1
5 1 4
3 9 2
2 8 4
4 3 2
### 範例輸出 3
67
:::
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int C, n;
cin >> C >> n;
vector<int> dp(C + 1, 0);
for (int i = 0; i < n; ++i) {
int w, v, k;
cin >> w >> v >> k;
for (int j = 1; k > 0; j <<= 1) {
int num = min(j, k);
int weight = w * num;
int value = v * num;
for (int c = C; c >= weight; --c) {
dp[c] = max(dp[c], dp[c - weight] + value);
}
k -= num;
}
}
cout << dp[C] << endl;
return 0;
}
```
Sign in with Wallet
Connect another wallet