目錄
回溯算法--01背包問題
[算法描述]
[回溯法基本思想]
法一：
法二：?
代碼：
?運行結(jié)果
代碼改進?
回溯算法--01背包問題
[算法描述]
0-1背包問題是子集選取問題。一般情況下，0-1背包問題是NP完全問題。0-1背包問題的解空間可以用子集樹表示。解0-1背包問題的回溯法與解裝載問題的回溯法十分相似。在搜索解空間樹時，只要其左兒子節(jié)點是一個可行的節(jié)點，搜索就進入其左子樹;而當(dāng)右子樹中有可能包含最優(yōu)解時才進入右子樹搜索，否則將右子樹剪去。設(shè)r是當(dāng)前剩余物品價值總和；cp是當(dāng)前價值；bestp是當(dāng)前最優(yōu)價值。當(dāng)cp+r<=bestp時，可剪去右子樹。計算右子樹中解的上界的更好的辦法是，將剩余物品依其單位重量價值排序，然后依次裝入物品，直至裝不下時，再裝入該物品的一部分而裝滿背包，由此得到的價值是右子樹的上界。
0--1背包的一個實例：
n=3, c=50,
w={10，30，20},
v(p)={60，120，100}的
0-1背包問題的最優(yōu)解和最優(yōu)值。<w為重量，v為價值量，n為物品個數(shù)，c為背包容量>
?
[回溯法基本思想]
確定了解空間的組織結(jié)構(gòu)后，【回溯法從開始節(jié)點（根節(jié)點）出發(fā)，以深度優(yōu)先搜索整個解空間。這個開始的節(jié)點為活節(jié)點，同時成為當(dāng)前的擴展節(jié)點。在當(dāng)前的擴展節(jié)點處，搜素向縱深方向移至一個新節(jié)點。這個新節(jié)點就成為新的活節(jié)點，并成為當(dāng)前擴展節(jié)點。如果當(dāng)前節(jié)點處不能再向縱深方向移動，則當(dāng)前擴展節(jié)點為死節(jié)點。此時，應(yīng)往回移動到最近的一個活節(jié)點處?；厮莘ㄒ赃@種方式遞歸的在解空間中搜素，直至找到所有符合要求的解或解空間中已無活節(jié)點?！浚瓷疃葍?yōu)先搜索）
【優(yōu)化方法】
剪枝（一）：當(dāng)前決策放入的物品總重量已經(jīng)大于背包容量時，沒有必要繼續(xù)決策，此時可以將其左子樹剪掉。
剪枝（二）：如果將當(dāng)前擴展節(jié)點后剩下的所有物品都裝入還沒有目前已求得的最優(yōu)值大的話，就不在進行決策了，直接返回。
遞歸回溯時，在當(dāng)前擴展節(jié)點處會通過設(shè)置約束函數(shù)和限界函數(shù)。不滿足條件的，剪去相應(yīng)的子樹
【0-1背包算法分析】
對于0-1背包問題，可用一顆完全二叉樹表示其解空間，針對上述實例（n=5），解空間樹有32個可能的解，解空間樹如下圖所示。
法一：
回溯算法是一種解決問題的通用算法，能夠在一個問題的所有解空間中，按深度優(yōu)先的策略搜索，直到找到所需要的解或者搜索完整個解空間都沒有找到解。0-1背包問題是指在限制背包容量的情況下，在一堆物品中選擇一部分，使得這些物品的總價值最大。
C++ 設(shè)計回溯算法解決 0-1 背包問題的思路如下：
- 定義一個全局?jǐn)?shù)組 max_value，用于存儲當(dāng)前找到的最大總價值；
- 定義一個局部數(shù)組 current_weight，用于存儲當(dāng)前已選物品的總重量；
- 定義一個遞歸函數(shù) backpack，用于搜索某一層的所有可能性；
- 在 backpack 函數(shù)中，首先判斷是否已經(jīng)遍歷完所有物品，如果是則更新數(shù)組 max_value；
- 如果還沒有處理完所有物品，則需要對當(dāng)前物品進行判斷。如果當(dāng)前物品的重量加上當(dāng)前已選物品的總重量仍然小于等于背包容量，則將當(dāng)前物品加入已選物品中，并進入下一層搜索。否則，不加入當(dāng)前物品，并進入下一層搜索。
- 在遞歸返回后，需要將當(dāng)前物品從已選物品中刪除，以方便下一次搜索。
一個簡單的 C++ 回溯算法解決 0-1 背包問題的示例代碼如下：
/*
* 回溯算法---0-1背包問題
*/
#include <iostream>
using namespace std;
const int max_n = 10;
const int capacity = 50;
int w[] = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 }; // 物品重量數(shù)組
int v[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; // 物品價值數(shù)組
bool selected[max_n]; // 記錄物品是否被選擇
int current_weight = 0; // 當(dāng)前已選物品的總重量
int max_value = 0; // 已找到的最大總價值
// backpack 函數(shù)用于搜索某一層的所有可能性
void backpack(int i) {
if (i == max_n) { // 如果已經(jīng)遍歷完所有物品，則更新 max_value
if (current_weight <= capacity && max_value < v[i]) {
max_value = v[i];
}
return;
}
if (current_weight + w[i] <= capacity) { // 如果能將當(dāng)前物品加入背包
selected[i] = true;
current_weight += w[i];
backpack(i + 1); // 進入下一層
current_weight -= w[i]; // 遞歸返回后，需要將當(dāng)前物品從已選物品中刪除
selected[i] = false;
}
backpack(i + 1); // 進入下一層
}
int main() {
backpack(0); // 從第一個物品開始搜索
cout << "最大總價值為：" << max_value << endl;
return 0;
}
法二：?
代碼：
頭文件：
#pragma once
#include<iostream>
#include<cmath>
#include<vector>
#include < algorithm>
using namespace std;源文件：
/*
* 回溯算法--01背包
*/
#include"01背包頭文件.h"
const int NUM = 50;
int c; //背包容納的重量
int n; //物品數(shù)量
int cw; //當(dāng)前重量
int cv; //當(dāng)前價值
int bestv; //當(dāng)前最優(yōu)價值
//描述每個物品的數(shù)據(jù)結(jié)構(gòu)
struct Object {
int w; //物品的重量
int v; //物品的價值
double d; //物品的單位價值重量比（d=v/w）
}Q[NUM]; //物品的數(shù)組
bool cmp(Object a,Object b) {
if (a.d>b.d){
return true;
}
else{
return false;
}
}
//限界函數(shù)Bound()的實現(xiàn)
//形參i是回溯的深度
int Bound(int i) {
int cleft = c - cw; // 背包剩余容納的重量
double b = cv; // 上界價值
while (i < n && Q[i].w <= cleft) { // 盡量裝滿背包
cleft -= Q[i].w;
b += Q[i].v;
i++;
}
if (i < n) { // 剩余空間不足以容納物品 i 時，將物品 i 分配到背包中，直到背包裝滿
b += 1.0 * Q[i].v / Q[i].w * cleft;
}
return b;
}
//形參i是回溯的深度，從0開始
void backtrack(int i){
if (i + 1 > n) {
bestv = cv;
return;
}
//進入左子樹搜索
if(cw+Q[i].w<=c) {
cw = cw + Q[i].w;
cv = cv + Q[i].v;
backtrack(i + 1);
cw = cw - Q[i].w;
cv = cv - Q[i].v;
}
//進入右子樹搜索
if(Bound(i+1)>bestv){
backtrack(i + 1);
}
}
int main() {
cin >> c >> n; //輸入背包容納的重量和物品數(shù)量
for (int i = 0; i < n; i++) {
cin >> Q[i].w >> Q[i].v; //輸入物品的重量和物品的價值
Q[i].d = 1.0 * Q[i].v / Q[i].w; //物品的單位價值重量比（d=v/w）
}
//排序
sort(Q, Q + n, cmp);
backtrack(0);
cout << "最大總價值為：" << bestv << endl;
return 0;
}?運行結(jié)果
代碼改進?
上面的代碼已經(jīng)實現(xiàn)了 01 背包問題的求解，但是還有一些需要改進的地方，以下是我的建議：
-
你在回溯函數(shù) backtrack 中使用遞歸的方式進行搜索。雖然遞歸可以使得代碼更加簡潔，但是如果物品數(shù)量較大時，可能會導(dǎo)致棧溢出的問題。因此，建議采用迭代的方式進行搜索，使用一個棧來存儲搜索狀態(tài)。
-
在你的排序函數(shù)中，其實不必寫成一個 bool 類型的函數(shù)，直接寫成一個比較函數(shù)即可。例如：
bool cmp(Object a, Object b) {
return a.d > b.d;
}
3.你在計算排序后的上界時，可能會出現(xiàn)除數(shù)為 0 的情況（當(dāng)背包容量為 0 時）。因此，在計算物品的單位價值時，可以加上一個特判，例如：
if (Q[i].w == 0) {
Q[i].d = 0;
} else {
Q[i].d = 1.0 * Q[i].v / Q[i].w;
}
4.下面是修改過的代碼：
/*
* 01 背包問題求解，回溯法實現(xiàn)
* 輸入格式：
* 第一行包含背包容量 c 和物品數(shù)量 n，以空格分隔；
* 接下來 n 行，每行包含一個物品的重量和價值，以空格分隔。
* 輸出格式：
* 最大總價值
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 50;
struct Object {
int w, v; // 物品重量和價值
double d; // 單位價值
};
bool cmp(Object a, Object b) {
return a.d > b.d;
}
int main() {
int c, n;
cin >> c >> n;
vector<Object> items(n);
for (int i = 0; i < n; i++) {
cin >> items[i].w >> items[i].v;
if (items[i].w == 0) {
items[i].d = 0;
} else {
items[i].d = 1.0 * items[i].v / items[i].w;
}
}
sort(items.begin(), items.end(), cmp); // 按單位價值排序
int bestv = 0; // 當(dāng)前最優(yōu)解
vector<int> path(n); // 存儲當(dāng)前搜索路徑
int i = 0; // 當(dāng)前搜索的物品編號
int cw = 0; // 當(dāng)前背包中物品的總重量
int cv = 0; // 當(dāng)前背包中物品的總價值
while (true) {
if (i >= n) { // 遍歷完了所有物品，回溯
if (bestv < cv) {
bestv = cv;
}
if (path.empty()) {
break; // 遍歷完了所有狀態(tài)，退出
}
i = path.back(); // 取出上一個搜索的物品
path.pop_back();
cw -= items[i].w;
cv -= items[i].v;
i++; // 進入右子樹搜索
} else if (cw + items[i].w <= c) { // 左子樹搜索
path.push_back(i);
cw += items[i].w;
cv += items[i].v;
i++; // 進入左子樹搜索
} else { // 右子樹搜索
double bound = cv + (c - cw) * items[i].d; // 計算上界
if (bound < bestv) {
if (path.empty()) {
break; // 遍歷完了所有狀態(tài)，退出
}
i = path.back(); // 取出上一個搜索的物品
path.pop_back();
cw -= items[i].w;
cv -= items[i].v;
i++; // 進入右子樹搜索
} else {
i++; // 進入左子樹搜索
}
}
}
cout << bestv << endl;
return 0;
}
這段代碼實現(xiàn)了 01 背包問題的回溯算法求解，并且采用了剪枝策略進行優(yōu)化，基本思路如下：
首先，讀入背包容量 c 和物品數(shù)量 n，以及每個物品的重量和價值。
將物品按單位價值從大到小排序，這里采用了 C++ STL 中的 sort 函數(shù)。
從第一個物品開始進行搜索，使用一個棧來保存搜索路徑，路徑上的每個節(jié)點包含當(dāng)前已選中的物品編號、當(dāng)前背包中已裝載的物品總重量和總價值。
在搜索過程中，對于每個節(jié)點，分別考慮進入其左子樹和右子樹兩種情況。左子樹表示當(dāng)前物品被選擇放入背包，進入左子樹后要將物品的重量和價值加入到當(dāng)前背包中，并更新搜索路徑；右子樹表示當(dāng)前物品不放入背包，進入右子樹后只需要更新搜索路徑即可。
在進入下一個節(jié)點之前，使用剪枝策略計算這個節(jié)點的上界。這里使用了線性松弛法（Linear Relaxation），即假設(shè)當(dāng)前物品可以部分裝入背包中，按單位價值從大到小的順序裝入物品直到背包裝滿，則此時背包中物品的總價值加上剩余空間能夠容納的物品的單位價值乘以其重量即為當(dāng)前節(jié)點的上界。如果計算出來的上界小于當(dāng)前已知的最優(yōu)解，則可以剪枝，放棄進入左子樹的搜索，直接進入右子樹。因為進入左子樹的搜索必然不會得到更優(yōu)的解。
當(dāng)遍歷完所有節(jié)點后，輸出當(dāng)前的最優(yōu)解即可。
總體而言，這段代碼實現(xiàn)了一個簡潔高效的 01 背包問題求解算法。文章來源：http://www.zghlxwxcb.cn/news/detail-405524.html
?文章來源地址http://www.zghlxwxcb.cn/news/detail-405524.html
到了這里，關(guān)于回溯算法--01背包問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
