1.編寫求解Hanoi漢諾塔的遞歸算法代碼，輸出移動過程，并統計總移動次數。 對不同規模的漢諾塔，給出測試的結果
#include <stdio.h>
#include <time.h>
int moveCount = 0;
void hanoi(int n,char source,char auxiliary,char target) {if (n==1) {moveCount++; printf("Move disk 1 from %c to %c\n", source, target);return;}hanoi(n - 1, source, target, auxiliary);moveCount++;printf("Move disk %d from %c to %c\n", n, source, target);hanoi(n - 1, auxiliary, source, target);
}
int main() {int n;printf("Enter the number of disks: ");scanf("%d", &n);clock_t start_time = clock();hanoi(n, 'A', 'B', 'C');printf("Total moves: %d\n", moveCount);clock_t end_time = clock();double time_taken = ((double)(end_time - start_time)) / CLOCKS_PER_SEC;printf("Total moves: %d\n", moveCount);printf("Time taken: %f seconds\n", time_taken);double theoretical_moves = (1 << n) - 1; printf("Theoretical moves (2^%d-1): %f\n", n, theoretical_moves);return 0;
}2.編寫程序實現2個有序數組的合并，并輸出基本操作（比較、移動）的次數。
#include <stdio.h>
void merge(int a[], int n1, int b[], int n2, int c[], int *comp, int *move);
int main() {int n1, n2;printf("請輸入第一個數組的大小: ");scanf("%d", &n1);int a[n1];printf("請輸入第一個數組的元素: ");for (int i = 0; i < n1; i++) {scanf("%d", &a[i]);}printf("請輸入第二個數組的大小: ");scanf("%d", &n2);int b[n2];printf("請輸入第二個數組的元素: ");for (int i = 0; i < n2; i++) {scanf("%d", &b[i]);}int c[n1 + n2];int comp = 0, move = 0;merge(a, n1, b, n2, c, &comp, &move);printf("合并后的數組: ");for (int i = 0; i < n1 + n2; i++) {printf("%d ", c[i]);}printf("\n");printf("比較操作次數: %d\n", comp);printf("移動操作次數: %d\n", move);return 0;
}
void merge(int a[], int n1, int b[], int n2, int c[], int *comp, int *move) {int i = 0, j = 0, k = 0;while (i < n1 && j < n2) {(*comp)++; if (a[i] < b[j]) {c[k++] = a[i++]; (*move)++;} else {c[k++] = b[j++]; (*move)++;}}while (i < n1) {c[k++] = a[i++]; (*move)++;}while (j < n2) {c[k++] = b[j++]; (*move)++;}
}3.使用蠻力法計算平面上最接近的兩點之間的距離，理解O(n^2)時間復雜度的影響
#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
#include <cstdlib>
#include <ctime>
using namespace std;
struct Point {double x, y;Point(double a, double b) {x = a;y = b;}
};
int main() {srand(time(0)); int numPoints = 10; vector<Point> points; for (int i = 0; i < numPoints; i++) {double x = rand() % 100; double y = rand() % 100;points.push_back(Point(x, y)); }cout << "隨機生成的點：" << endl; for (size_t i = 0; i < points.size(); i++) { cout << "(" << points[i].x << ", " << points[i].y << ")" << endl;}double minDist = numeric_limits<double>::max(); for (int i = 0; i < numPoints; i++) {for (int j = i + 1; j < numPoints; j++) { double dx = points[i].x - points[j].x;double dy = points[i].y - points[j].y;double dist = sqrt(dx * dx + dy * dy); if (dist < minDist) {minDist = dist;}}}cout << "最近兩點之間的最短距離：" << minDist << endl;return 0;
}
4.求有序數組中兩個數的和等于目標值
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {int left = 0;int right = numsSize - 1;int* result = (int*)malloc(2 * sizeof(int));if (result == NULL) {return NULL;}while (left < right) {int sum = nums[left] + nums[right];if (sum == target) {result[0] = left;result[1] = right;*returnSize = 2;return result;} else if (sum < target) {left++;} else {right--;}}*returnSize = 0;free(result);return NULL;
}
void parseInput(const char* input, int** nums, int* numsSize, int* target) {char* temp = strdup(input);char* token = strtok(temp, "=[], ");token = strtok(NULL, "=[], ");*numsSize = 0;while (token != NULL && strcmp(token, "target") != 0) {(*numsSize)++;token = strtok(NULL, "=[], ");}*nums = (int*)malloc(*numsSize * sizeof(int));if (*nums == NULL) {printf("內存分配失敗\n");exit(1);}token = strtok(temp, "=[], ");token = strtok(NULL, "=[], ");for (int i = 0; i < *numsSize; i++) {(*nums)[i] = atoi(token);token = strtok(NULL, "=[], ");}token = strtok(NULL, "=[], ");*target = atoi(token);free(temp);
}
int main() {char input[1000];printf("請按照 nums=[1, 3, 5, 7, 9], target=10 的格式輸入: ");fgets(input, sizeof(input), stdin);input[strcspn(input, "\n")] = 0; int* nums;int numsSize;int target;parseInput(input, &nums, &numsSize, &target);int returnSize;int* result = twoSum(nums, numsSize, target, &returnSize);if (result != NULL) {printf("[%d, %d]\n", result[0], result[1]);free(result);} else {printf("未找到符合條件的兩個數\n");}free(nums);return 0;
}
5.給定一組物品，每個物品有一個重量和一個價值。背包有一個最大承重限制。目標是從這些物品中選擇一部分裝入背包，使得背包中物品的總價值最大。與0/1背包問題不同，分數背包問題允許將物品分割成任意大小（即可以選擇物品的一部分裝入背包）。//輸入：物品數量 n、每個物品的重量和價值 、背包的最大承重W
#include <stdio.h>
#include <stdlib.h>typedef struct {int weight;int value;double ratio;
} Item;
int compare(const void *a, const void *b) {Item *itemA = (Item *)a;Item *itemB = (Item *)b;if (itemA->ratio < itemB->ratio)return 1;else if (itemA->ratio > itemB->ratio)return -1;return 0;
}
double fractionalKnapsack(int n, Item items[], int capacity) {for (int i = 0; i < n; i++) {items[i].ratio = (double)items[i].value / items[i].weight;}qsort(items, n, sizeof(Item), compare);double totalValue = 0.0;int currentCapacity = capacity;for (int i = 0; i < n; i++) {if (currentCapacity >= items[i].weight) {totalValue += items[i].value;currentCapacity -= items[i].weight;} else {totalValue += currentCapacity * items[i].ratio;break;}}return totalValue;
}
int main() {int n, capacity;printf("請輸入物品的數量: ");scanf("%d", &n);Item *items = (Item *)malloc(n * sizeof(Item));if (items == NULL) {printf("內存分配失敗\n");return 1;}printf("請依次輸入每個物品的重量和價值:\n");for (int i = 0; i < n; i++) {scanf("%d %d", &items[i].weight, &items[i].value);}printf("請輸入背包的最大承重: ");scanf("%d", &capacity);double maxValue = fractionalKnapsack(n, items, capacity);printf("背包中物品的最大總價值為: %.2f\n", maxValue);free(items);return 0;
} 6.在區間調度問題中，給定 n 個作業，每個作業由一個時間區間 [s_i, f_i]（s_i 為開始時間，f_i 為結束時間）表示。每個作業互不兼容（即不能同時運行兩個作業）。目標是在不重疊的情況下安排最多的作業。
#include <stdio.h>
#include <stdlib.h>
typedef struct {int start;int end;int index;
} Job;
int compare(const void *a, const void *b) {Job *jobA = (Job *)a;Job *jobB = (Job *)b;return jobA->end - jobB->end;
}
int main() {int n;printf("請輸入任務數: ");scanf("%d", &n);Job *jobs = (Job *)malloc(n * sizeof(Job));if (jobs == NULL) {printf("內存分配失敗\n");return 1;}// 輸入每個作業的開始和結束時間for (int i = 0; i < n; i++) {printf("請輸入第 %d 個作業的開始時間和結束時間: ", i + 1);scanf("%d %d", &jobs[i].start, &jobs[i].end);jobs[i].index = i + 1;}// 按結束時間排序qsort(jobs, n, sizeof(Job), compare);int selectedJobs[100];int count = 0;// 選擇第一個作業selectedJobs[count++] = jobs[0].index;int prevEnd = jobs[0].end;// 貪心選擇作業for (int i = 1; i < n; i++) {if (jobs[i].start >= prevEnd) {selectedJobs[count++] = jobs[i].index;prevEnd = jobs[i].end;}}// 輸出結果printf("選出的作業個數: %d\n", count);printf("選出的作業序列: ");for (int i = 0; i < count; i++) {printf("%d ", selectedJobs[i]);}printf("\n");free(jobs);return 0;
} 7.
7.1選擇鄰接矩陣或鄰接表作為圖的存儲結構.使用 Prim 算法求解最小生成樹。輸出最小生成樹的總權值和具體選取的邊。
#include <stdio.h>
#include <limits.h>
#include <stdlib.h> // 添加這一行
// 找到距離最小生成樹最近且未被包含的頂點
int minKey(int key[], int mstSet[], int V) {int min = INT_MAX, min_index;for (int v = 0; v < V; v++) {if (mstSet[v] == 0 && key[v] < min) {min = key[v];min_index = v;}}return min_index;
}
// 打印最小生成樹
void printMST(int parent[], int **graph, int V) {int total_weight = 0;printf("Edge \tWeight\n");for (int i = 1; i < V; i++) {printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);total_weight += graph[i][parent[i]];}printf("Total weight of MST: %d\n", total_weight);
}
// Prim 算法實現
void primMST(int **graph, int V) {int *parent = (int *)malloc(V * sizeof(int)); // 存儲最小生成樹中每個頂點的父節點int *key = (int *)malloc(V * sizeof(int)); // 存儲每個頂點到最小生成樹的最小權值int *mstSet = (int *)malloc(V * sizeof(int)); // 標記頂點是否已被包含在最小生成樹中// 初始化所有頂點的 key 值為無窮大，mstSet 為 falsefor (int i = 0; i < V; i++) {key[i] = INT_MAX;mstSet[i] = 0;}// 從頂點 0 開始構建最小生成樹key[0] = 0;parent[0] = -1; // 頂點 0 是根節點，沒有父節點// 構建最小生成樹，直到包含所有頂點for (int count = 0; count < V - 1; count++) {// 找到距離最小生成樹最近且未被包含的頂點int u = minKey(key, mstSet, V);// 將該頂點標記為已包含在最小生成樹中mstSet[u] = 1;// 更新與該頂點相鄰且未被包含的頂點的 key 值和父節點for (int v = 0; v < V; v++) {if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {parent[v] = u;key[v] = graph[u][v];}}}// 打印最小生成樹printMST(parent, graph, V);// 釋放動態分配的內存free(parent);free(key);free(mstSet);
}
int main() {int V;printf("請輸入圖的頂點數量: ");scanf("%d", &V);// 動態分配鄰接矩陣的內存int **graph = (int **)malloc(V * sizeof(int *));for (int i = 0; i < V; i++) {graph[i] = (int *)malloc(V * sizeof(int));}printf("請輸入圖的鄰接矩陣（%d x %d）:\n", V, V);for (int i = 0; i < V; i++) {for (int j = 0; j < V; j++) {scanf("%d", &graph[i][j]);}}// 調用 Prim 算法求解最小生成樹primMST(graph, V);// 釋放鄰接矩陣的內存for (int i = 0; i < V; i++) {free(graph[i]);}free(graph);return 0;
}7.2進階：采用優先隊列（堆優化）版本的Prim算法，提高效率。
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// 定義一個結構體來表示圖的邊
typedef struct {int vertex;int weight;
} Edge;
// 定義一個結構體來表示優先隊列的元素
typedef struct {int vertex;int key;
} QueueElement;
// 交換兩個隊列元素
void swap(QueueElement *a, QueueElement *b) {QueueElement temp = *a;*a = *b;*b = temp;
}
// 最小堆化
void minHeapify(QueueElement *heap, int *pos, int n, int i) {int smallest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && heap[left].key < heap[smallest].key)smallest = left;if (right < n && heap[right].key < heap[smallest].key)smallest = right;if (smallest != i) {// 更新位置數組pos[heap[smallest].vertex] = i;pos[heap[i].vertex] = smallest;swap(&heap[smallest], &heap[i]);minHeapify(heap, pos, n, smallest);}
}
// 從堆中提取最小元素
QueueElement extractMin(QueueElement *heap, int *pos, int *n) {QueueElement root = heap[0];QueueElement last = heap[*n - 1];// 將最后一個元素移到根節點heap[0] = last;// 更新位置數組pos[root.vertex] = *n - 1;pos[last.vertex] = 0;// 減小堆的大小(*n)--;// 最小堆化minHeapify(heap, pos, *n, 0);return root;
}
// 減小某個頂點的 key 值
void decreaseKey(QueueElement *heap, int *pos, int n, int v, int key) {int i = pos[v];heap[i].key = key;while (i && heap[i].key < heap[(i - 1) / 2].key) {// 更新位置數組pos[heap[i].vertex] = (i - 1) / 2;pos[heap[(i - 1) / 2].vertex] = i;swap(&heap[i], &heap[(i - 1) / 2]);i = (i - 1) / 2;}
}
// 檢查頂點是否在堆中
int isInHeap(int *pos, int v, int n) {return pos[v] < n;
}// 打印最小生成樹
void printMST(int parent[], int **graph, int V) {int total_weight = 0;printf("Edge \tWeight\n");for (int i = 1; i < V; i++) {printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);total_weight += graph[i][parent[i]];}printf("Total weight of MST: %d\n", total_weight);
}
// 堆優化的 Prim 算法
void primMST(int **graph, int V) {int *parent = (int *)malloc(V * sizeof(int)); // 存儲最小生成樹中每個頂點的父節點int *key = (int *)malloc(V * sizeof(int)); // 存儲每個頂點到最小生成樹的最小權值int *pos = (int *)malloc(V * sizeof(int)); // 存儲每個頂點在堆中的位置QueueElement *heap = (QueueElement *)malloc(V * sizeof(QueueElement));// 初始化所有頂點的 key 值為無窮大，parent 為 -1for (int i = 0; i < V; i++) {key[i] = INT_MAX;parent[i] = -1;pos[i] = i;heap[i].vertex = i;heap[i].key = INT_MAX;}// 從頂點 0 開始構建最小生成樹key[0] = 0;heap[0].key = 0;int heapSize = V;while (heapSize > 0) {// 提取最小 key 值的頂點QueueElement minElement = extractMin(heap, pos, &heapSize);int u = minElement.vertex;// 遍歷所有相鄰頂點for (int v = 0; v < V; v++) {if (graph[u][v] && isInHeap(pos, v, heapSize) && graph[u][v] < key[v]) {key[v] = graph[u][v];parent[v] = u;decreaseKey(heap, pos, heapSize, v, key[v]);}}}// 打印最小生成樹printMST(parent, graph, V);// 釋放動態分配的內存free(parent);free(key);free(pos);free(heap);
}
int main() {int V;printf("請輸入圖的頂點數量: ");scanf("%d", &V);// 動態分配鄰接矩陣的內存int **graph = (int **)malloc(V * sizeof(int *));for (int i = 0; i < V; i++) {graph[i] = (int *)malloc(V * sizeof(int));}printf("請輸入圖的鄰接矩陣（%d x %d）:\n", V, V);for (int i = 0; i < V; i++) {for (int j = 0; j < V; j++) {scanf("%d", &graph[i][j]);}}// 調用堆優化的 Prim 算法求解最小生成樹primMST(graph, V);// 釋放鄰接矩陣的內存for (int i = 0; i < V; i++) {free(graph[i]);}free(graph);return 0;
}
8.[逆序數算法】編寫一個函數?countInversions，用于計算整數數組中的逆序對數。逆序對是指滿足條件?i < j?且?arr[i] > arr[j]?的數對?(i, j)。
#include <stdio.h>
#include <stdlib.h>
int merge(int arr[], int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;int L[n1], R[n2];int i, j, k;int inversions = 0;for (i = 0; i < n1; i++)L[i] = arr[left + i];for (j = 0; j < n2; j++)R[j] = arr[mid + 1 + j];i = 0; j = 0; k = left; while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;inversions += (n1 - i);}k++;}while (i < n1) {arr[k] = L[i];i++;k++;}while (j < n2) {arr[k] = R[j];j++;k++;}return inversions;
}
int mergeSort(int arr[], int left, int right) {int inversions = 0;if (left < right) {int mid = left + (right - left) / 2;inversions += mergeSort(arr, left, mid);inversions += mergeSort(arr, mid + 1, right);inversions += merge(arr, left, mid, right);}return inversions;
}
int countInversions(int arr[], int n) {return mergeSort(arr, 0, n - 1);
}int main() {char input[1000];int arr[1000];int n = 0;fgets(input, sizeof(input), stdin);int i = 1;while (input[i] != '\0') {if (input[i] == ']') {break;}if (input[i] != ' ' && input[i] != ',') {int num = 0;int sign = 1;if (input[i] == '-') {sign = -1;i++;}while (input[i] >= '0' && input[i] <= '9') {num = num * 10 + (input[i] - '0');i++;}arr[n++] = sign * num;} else {i++;}}int inversions = countInversions(arr, n);printf(" %d\n", inversions);return 0;
}9.實現 Median of Medians 算法，用于在無序數組中找出第 k 小的元素。
#include <stdio.h>
#include <stdlib.h>
// 交換函數
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}
// 插入排序（用于小數組排序和驗證用）
void insertionSort(int arr[], int left, int right) {for (int i = left + 1; i <= right; i++) {int key = arr[i];int j = i - 1;while (j >= left && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}
// 獲取一組的中位數
int getMedian(int arr[], int left, int right) {insertionSort(arr, left, right);return arr[(left + right) / 2];
}
// 分區操作
int partition(int arr[], int left, int right, int pivot) {int i;for (i = left; i <= right; i++) {if (arr[i] == pivot) break;}swap(&arr[i], &arr[right]);int storeIndex = left;for (i = left; i < right; i++) {if (arr[i] < pivot) {swap(&arr[i], &arr[storeIndex]);storeIndex++;}}swap(&arr[storeIndex], &arr[right]);return storeIndex;
}
// 主算法：Median of Medians
int selectKth(int arr[], int left, int right, int k) {int n = right - left + 1;if (n <= 5) {insertionSort(arr, left, right);return arr[left + k - 1];}int medianCount = (n + 4) / 5;int *medians = (int *)malloc(medianCount * sizeof(int));for (int i = 0; i < medianCount; i++) {int subLeft = left + i * 5;int subRight = subLeft + 4;if (subRight > right) subRight = right;medians[i] = getMedian(arr, subLeft, subRight);}int medOfMed = selectKth(medians, 0, medianCount - 1, (medianCount + 1) / 2);free(medians);int pivotIndex = partition(arr, left, right, medOfMed);int rank = pivotIndex - left + 1;if (k == rank)return arr[pivotIndex];else if (k < rank)return selectKth(arr, left, pivotIndex - 1, k);elsereturn selectKth(arr, pivotIndex + 1, right, k - rank);
}
// 主函數
int main() {int n, k;printf("請輸入數組長度 n：");scanf("%d", &n);if (n <= 0) {printf("錯誤：數組長度必須為正數！\n");return 1;}int *arr = (int *)malloc(n * sizeof(int));int *arrCopy = (int *)malloc(n * sizeof(int));printf("請輸入 %d 個整數：\n", n);for (int i = 0; i < n; i++) {scanf("%d", &arr[i]);arrCopy[i] = arr[i]; // 復制一份用于驗證}printf("請輸入要查找的第 k 小元素 (1 ~ %d)：", n);scanf("%d", &k);if (k < 1 || k > n) {printf("錯誤：k 值不合法！\n");free(arr);free(arrCopy);return 1;}int result = selectKth(arr, 0, n - 1, k);printf("第 %d 小的元素是：%d\n", k, result);// 驗證部分insertionSort(arrCopy, 0, n - 1);int expected = arrCopy[k - 1];if (result == expected) {printf("驗證結果：正確\n");} else {printf("驗證結果：錯誤 （應為 %d）\n", expected);}free(arr);free(arrCopy);return 0;
}
10.掌握動態規劃求解0-1背包問題的基本思想與實現步驟。
#?1.給定若干個物品，每個物品有重量和價值，背包容量為一定的正整數。
# 2.實現一個動態規劃算法，求解在給定容量下，能夠裝入背包的最大總價值。
# 3.輸出最終最大價值，以及用于構造該最優值的物品組合（可選）。
# 4.顯示動態規劃中構建的二維數組 dp[i][j] 的過程（物品編號 i、容量 j）。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 打印二維數組 dp
void printDP(const vector< vector<int> >& dp) {for (int i = 0; i < dp.size(); i++) {for (int j = 0; j < dp[i].size(); j++) {cout << dp[i][j] << " ";}cout << endl;}cout << endl;
}
// 回溯找出選擇的物品
vector<int> findSelectedItems(const vector< vector<int> >& dp, const vector<int>& weights, const vector<int>& values, int n, int capacity) {vector<int> selectedItems;int i = n, j = capacity;while (i > 0 && j > 0) {if (dp[i][j] != dp[i - 1][j]) {selectedItems.push_back(i);j -= weights[i - 1];}i--;}vector<int> reversedItems;for (int k = selectedItems.size() - 1; k >= 0; k--) {reversedItems.push_back(selectedItems[k]);}return reversedItems;
}
int main() {int n; // 物品數量int capacity; // 背包容量cout << "請輸入物品數量: ";cin >> n;cout << "請輸入背包容量: ";cin >> capacity;vector<int> weights(n);vector<int> values(n);cout << "請依次輸入每個物品的 編號 重量 價值（格式：編號 重量 價值）：" << endl;for (int i = 0; i < n; i++) {int id;cout << "物品 " << i + 1 << ": ";cin >> id >> weights[i] >> values[i];}// 初始化二維數組 dpvector< vector<int> > dp(n + 1);for (int i = 0; i <= n; i++) {dp[i].resize(capacity + 1, 0);}// 動態規劃過程for (int i = 1; i <= n; i++) {for (int j = 0; j <= capacity; j++) {if (j < weights[i - 1]) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);}}// 輸出每一步的二維數組變化情況cout << "Step " << i << ":" << endl;printDP(dp);}// 輸出最大價值int maxValue = dp[n][capacity];cout << "最大價值: " << maxValue << endl;// 找出選擇的物品vector<int> selectedItems = findSelectedItems(dp, weights, values, n, capacity);cout << "選擇的物品編號: ";for (int i = 0; i < selectedItems.size(); i++) {cout << selectedItems[i] << " ";}cout << endl;return 0;
}
11.編寫程序，使用回溯法輸出給定整數序列的所有排列，例如輸入{1，2，3}
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;
// 回溯函數生成全排列
void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used) {if (path.size() == nums.size()) {for (int i = 0; i < path.size(); ++i) {cout << path[i] << " ";}cout << endl;return;}for (int i = 0; i < nums.size(); ++i) {if (!used[i]) {used[i] = true;path.push_back(nums[i]);backtrack(nums, path, used);path.pop_back();used[i] = false;}}
}
int main() {string input;getline(cin, input);istringstream iss(input);vector<int> nums;int num;while (iss >> num) {nums.push_back(num);}if (nums.empty()) {cout << "輸入不能為空！" << endl;return 1;}vector<int> path;vector<bool> used(nums.size(), false);backtrack(nums, path, used);return 0;
}
12、分支限界發求解0-1背包問題//給定一組物品，每個物品有重量wi和價值vi，以及一個容量為C的背包。要求選擇物品的子集，使得總重量不超過背包容量，且總價值最大。每個物品只能選或不選（0-1屬性）。
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
// 物品結構體
struct Item {int index;int weight;int value;double ratio;Item(int idx, int w, int v) : index(idx), weight(w), value(v) {ratio = (double)v / w;}
};
// 分支限界樹節點結構體
struct Node {int level;int value;int weight;double bound;vector<int> path;bool operator<(const Node& other) const {return bound < other.bound;}
};
// 上界計算函數
double computeBound(Node u, int n, int W, const vector<Item>& items) {if (u.weight >= W) return 0;double bound = u.value;int totalWeight = u.weight;for (int i = u.level; i < n; ++i) {if (totalWeight + items[i].weight <= W) {totalWeight += items[i].weight;bound += items[i].value;} else {int remain = W - totalWeight;bound += remain * items[i].ratio;break;}}return bound;
}
// 主算法
int knapsackBranchBound(int W, vector<Item>& items, vector<int>& bestPath) {sort(items.begin(), items.end(), [](const Item& a, const Item& b) {return a.ratio > b.ratio;});priority_queue<Node> pq;int maxValue = 0;Node root = {0, 0, 0, 0.0, {}};root.bound = computeBound(root, items.size(), W, items);pq.push(root);while (!pq.empty()) {Node current = pq.top(); pq.pop();if (current.bound <= maxValue || current.level == items.size())continue;// 包含當前物品Node include = current;Item item = items[current.level];include.level++;include.weight += item.weight;include.value += item.value;include.path.push_back(item.index);include.bound = computeBound(include, items.size(), W, items);if (include.weight <= W && include.value > maxValue) {maxValue = include.value;bestPath = include.path;}if (include.bound > maxValue)pq.push(include);// 不包含當前物品Node exclude = current;exclude.level++;exclude.bound = computeBound(exclude, items.size(), W, items);if (exclude.bound > maxValue)pq.push(exclude);}return maxValue;
}
int main() {int n, W;cout << "請輸入物品數量：";cin >> n;cout << "請輸入背包容量：";cin >> W;vector<int> weights(n), values(n);cout << "請輸入所有物品的重量：" << endl;for (int i = 0; i < n; ++i) {cin >> weights[i];}cout << "請輸入所有物品的價值：" << endl;for (int i = 0; i < n; ++i) {cin >> values[i];}vector<Item> items;for (int i = 0; i < n; ++i) {items.emplace_back(i + 1, weights[i], values[i]);}vector<int> selectedItems;int maxValue = knapsackBranchBound(W, items, selectedItems);cout << "\n最大價值：" << maxValue << endl;cout << "選擇物品：" << endl;for (int idx : selectedItems) {cout << " 物品" << idx << "（重量" << weights[idx - 1]<< "，價值" << values[idx - 1] << "）" << endl;}return 0;
}
