分支限界法是一種求解優化問題的算法，針對01背包問題，它可以通過在搜索過程中剪枝，減少搜索空間的大小，提高算法的效率。
具體來說，分支限界法會將當前狀態下的可行解集合分成若干個子集，每個子集代表一條搜索路徑，然后根據某種啟發式策略（如最大價值優先、最小重量優先等）對這些子集進行排序，選擇價值最大/重量最小的子集進行擴展，將其分成若干個子集，再重復上述過程，直到找到最優解或者搜索結束。
在求解01背包問題時，分支限界法每次擴展節點時，會判斷當前節點能否產生更優的解，如果不能，就進行剪枝，減少搜索空間。例如，如果當前節點已經超出了背包的容量限制，就可以直接剪枝，不再繼續擴展。在搜索過程中，分支限界法還會維護一個上界，即當前可行解集合中的最優解，如果當前節點的下界已經小于上界，也可以直接剪枝，不再繼續擴展。
分支限界法是一種高效、精確的求解優化問題的算法，但需要注意的是，它并不保證一定能找到最優解，因為搜索空間較大時，其時間復雜度可能會非常高。
代碼：
#include <stdio.h>
#include <stdlib.h>#define MAX_N 1000 // 最大物品數量
#define MAX_W 1000 // 最大背包容量int n; // 物品數量
int w[MAX_N]; // 物品重量
int v[MAX_N]; // 物品價值
int c; // 背包容量
int maxv; // 最大價值
int curw; // 當前背包重量
int curv; // 當前背包價值
int bestv[MAX_W]; // bestv[i]表示當前索引為i時，背包容量為i時的最大價值// 計算以j為索引、背包容量為c的情況下，能夠獲得的最大價值
int bound(int j, int c) {int b = curv;int leftw = c - curw;while (j < n && leftw >= w[j]) {leftw -= w[j];b += v[j];j++;}if (j < n) {b += leftw * v[j] / w[j];}return b;
}// 搜索第i個物品是否放入背包
void dfs(int i) {if (i == n) { // 達到葉子節點，更新最大價值maxv = curv;return;}// 不選第i個物品bestv[i+1] = bound(i+1, c); // 計算下一個物品的最大價值if (bestv[i+1] < maxv) { // 如果最大價值都小于當前最大價值，直接返回return;}dfs(i+1);// 選第i個物品if (curw + w[i] <= c) { // 可以放入背包curw += w[i];curv += v[i];if (curv > maxv) { // 更新最大價值maxv = curv;}bestv[i+1] = bound(i+1, c); // 計算下一個物品的最大價值if (bestv[i+1] > maxv) { // 如果最大價值比當前最大價值大，繼續搜索dfs(i+1);}curw -= w[i]; // 回溯curv -= v[i];}
}int main() {// 讀入數據scanf("%d%d", &n, &c);for (int i = 0; i < n; i++) {scanf("%d%d", &w[i], &v[i]);}// 初始化maxv = curv = 0;curw = 0;bestv[0] = bound(0, c);// 搜索dfs(0);// 輸出結果printf("%d\n", maxv);return 0;
}
分支限界法的思路如下：
- 按照某種規則先對問題求出一個下界，把問題分成可行和不可行兩種情況。對于可行的情況，可以計算出對應的最優解的上界（貪心法、動態規劃等）。
- 依次搜索所有可能的解，在搜索過程中，利用計算出的上界剪枝，即當某個節點的上界小于當前最優解時，可以直接返回上一層，省略掉這個分支。
- 在搜索過程中，記錄當前的最優解，并不斷更新。當達到葉子節點，即搜索結束時，返回最優解。
對于01背包問題，每個節點有兩種情況，即選或不選當前物品。對于每個節點，可以計算出剩余物品的最大價值，從而計算出當前節點可以達到的最大價值（上界）。用一個數組bestv記錄每個節點的最大價值，如果當前節點的上界小于當前最優解，直接返回；如果當前節點的最大價值比當前最優解大，繼續搜索。在搜索過程中，使用變量curw和curv記錄當前的背包重量和價值，變量maxv記錄當前的最大價值。
)
)
