實驗五、回溯法
一 實驗目的與要求
1、 了解回溯法的概念。
2、 掌握回溯法糾結問題基本步驟。
3、 了解回溯算法效率的分析方法
二 實驗内容
1、求解組合問題回溯求法
2、0/1背包問題分支求法
三、實驗題
1、編寫一個實驗程式，采用回溯法輸出自然數1~n中任取r個數的所有組合
實驗報告使用
#include <iostream>
#include <string.h>
using namespace std;
const int MAXSIZE = 100;
int g_iArr[MAXSIZE];
bool isOk()
{
int iTemp;
int iNext;
int iCur = 100000;
for(int j = g_iArr[0]; j >= 1; j--)
{
iNext = g_iArr[j];//第一個數
//判斷前面的數是否比自己大，正常的順序應該是前面大，後面小，如果不符合就是前面<=後面。現在拿到的第一個是最前面的
if( iCur <= iNext)
{
return false;
}
iCur = iNext;
}
return true;
}
void dfs(int n,int r)
{
for(int i = n ; i >= r ; i--)
{
//設定目前選中的元素為第一個，因為元素的選取是從大到小，是以為i
g_iArr[r] = i;
//遞歸基,當r減為1，說明成功了
if(r == 1)
{
if(isOk())
{
for(int j = g_iArr[0]; j >= 1; j--)
{
cout << g_iArr[j];
}
cout << endl;
}
}
//遞歸步，從剩餘n-1個數中挑選r-1個數
else
{
//添加限制條件，後面的大于前面，不能重複
dfs(n-1,r-1);
}
}
}
void process()
{
int n,r;
while(EOF != scanf("%d %d",&n,&r))
{
//要設定初始值,為什麼為r,g_iArr[r] = 就等于最大值了
g_iArr[0] = r;
dfs(n,r);
}
}
int main(int argc,char* argv[])
{
process();
getchar();
return 0;
學習更多的方法（回溯算法）
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100+50;
int n,r,a[maxn];
void dfs(int now){
if(now==n+1){
if(a[0]==r){
for(int i=1;i<=a[0];i++)cout<<a[i]<<' ';cout<<endl;
}
return ;
}
a[++a[0]]=now;
dfs(now+1);
a[0]--;
dfs(now+1);
}
int main(){
cin>>n>>r;
dfs(1);
return 0;
}
使用C語言實作
本部分未經過測試
文章目錄
組合：數字型
方法一
方法二
完整代碼
組合：字元型
組合：數字型
【問題】利用遞歸方法找出從自然數1,2,…,n中任取r個數的所有組合
【例如】n=5,r=3，所有組合為：
在這裡插入圖檔描述
方法一
【思路】
抽象問題：1,…,n中選r --> f(n,r)
從邊界n考慮，n要麼取，要麼不取 --> f(n,r) = f(n-1, r) + f(n-1, r-1)
退出條件：r==0時，就已經選完了
異常條件：n<r的時候
int a[50]; //存放組合的結果數組
void f(int n,int r,int m) {
// 從1,...n序列中選r個數字進行組合，目前已選m個數
// 【m了解】目前已選擇m個數 or 此次選擇的數放到a[m]的位置 or 結果數組的最後一位
int i;
if (n<r) return ; //異常條件
if (r==0) { //從1,...,n序列中選0個數字進行組合
// 列印輸出此次組合的結果
for (i=0; i<m; i++) printf("%d", a[i]);
printf("\n");
} else {
// 将n選入數組，指派到結果數組
a[m] = n;
f(n-1, r-1, m+1); //已經選了n這個數字-->從1,...,n-1選r-1個
//不選n
f(n-1, r, m); //n沒有選-->從1,...,n-1選r個
}
}
方法二
【代碼】
// 從1-n的數字中選r個數字
// 目前選的一個放入a[m]位置中
void C(int n, int r, int a[], int m) {
int i;
if (r==0) { //選完了
//輸出
for (i=0; i<m; i++) printf("%d", a[i]);
printf("\n");
} else {
// 在[r,n]的範圍内選一個數字放入a[m]
for (i=n; i>=r; i--) {
a[m] = i;
C(i-1, r-1, a, m+1);
}
}
}
【了解】用樹狀的形式輸出遞歸樹（先序）
樹狀的方式類似于這種https://blog.csdn.net/summer_dew/article/details/82937941
在這裡插入圖檔描述
完整代碼
方法一：
#include<stdio.h>
int a[50];
void f(int n,int r,int m) {
int i;
if (n<r) return ;
if (r==0) {
for (i=0; i<m; i++) printf("%d", a[i]);
printf("\n");
} else {
//選n
a[m] = n;
f(n-1, r-1, m+1);
//不選n
f(n-1, r, m);
}
}
int main() {
int n,r;
while (1) {
printf("輸入n與r，空格分割\n>>> ");
scanf("%d%d", &n, &r);
f(n, r, 0);
printf("\n");
}
return 0;
}
方法二：
#include<stdio.h>
// 從1-n的數字中選r個數字
// 目前選的一個放入a[m]位置中
void C(int n, int r, int a[], int m) {
int i;
// 以樹狀輸出遞歸樹
/*
for (i=0; i<m; i++) {
printf(" ");
}
printf( "C(%d,%d, '" , n,r);
for (i=0; i<m; i++) {
printf("%d ", a[i]);
}
printf("', %d)",m );
printf("\n");
*/
if (r==0) { // 選完了
// 輸出
for (i=0; i<m; i++) printf("%d", a[i]);
printf("\n");
} else {
// 在[r,n]的範圍内選一個數字放入a[m]
for (i=n; i>=r; i--) {
a[m] = i;
C(i-1, r-1, a, m+1);
}
}
}
int main() {
int n,r;
int a[50];
while (1) {
printf("輸入n與r，空格分割\n>>> ");
scanf("%d%d", &n, &r);
C(n, r, a, 0);
printf("\n");
}
return 0;
}
組合：字元型
【問題】從長度為n個字元串str中選出m個元素的可能
【思路】
在這裡插入圖檔描述
【代碼】
char *tmp; //中間結果
int top;
int count; //種數
//遞歸求組合數
void combination(char *str, int n, int m )
{
if( n < m || m == 0 ) return ; //case 1：不符合條件，傳回
combination( str+1, n-1, m ); //case 2：不包含目前元素的所有的組合
tmp[ top++ ] = str[0]; //case 3：包含目前元素
if( m == 1 ){ //case 3.1：截止到目前元素
printA( tmp, top );
printf("\n");
count++;
top--;
return;
}
combination( str+1, n-1, m-1); //case 3.2：包含目前元素但尚未截止
top--; //傳回前恢複top值
}
【了解】将遞歸樹進行先序輸出
樹狀的方式類似于這種https://blog.csdn.net/summer_dew/article/details/82937941
在這裡插入圖檔描述
【完整代碼】
#include<stdio.h>
#include<stdlib.h>
char *tmp; //中間結果
int top; //
int count; //種數
//列印長度為n的數組元素
void printA(char *str,int n)
{
int i;
for(i=0;i<n;i++){
printf("%c ",str[i]);
}
}
//遞歸求組合數
void combination(char *str, int n, int m )
{
if( n < m || m == 0 ) return ; //case 1：不符合條件，傳回
combination( str+1, n-1, m ); //case 2：不包含目前元素的所有的組合
tmp[ top++ ] = str[0]; //case 3：包含目前元素
if( m == 1 ){ //case 3.1：截止到目前元素
printA( tmp, top );
printf("\n");
count++;
top--;
return;
}
combination( str+1, n-1, m-1); //case 3.2：包含目前元素但尚未截止
top--; //傳回前恢複top值
}
int main()
{
int n,m;//存放資料的數組，及n和m
char *str;
printf("輸入n與m，用空格隔開\n>>> ");
scanf("%d%d",&n,&m);
str = (char *) malloc( sizeof(char) * n );
tmp = (char *) malloc( sizeof(char) * m );
printf("輸入字元串\n>>> ");
scanf("%s", str);
printf("\n%s %d中選取%d個", str, n, m);
combination( str, n, m );//求數組中所有數的組合
printf("總數%d\n", count);
return 0;
}
2、假設一個0/1背包問題是n=3，重量為w=（16,15,15），價值為v=(45,25,25),背包限重為W=30，求放入背包總重量小于等于W并且價值最大的解，設解向量為x=（x1,x2,x3）,請通過隊列式和優先隊列式（帶限制條件的）兩種分支限界法求解該問題。
層次
這個是分析
from
https://wenku.baidu.com/view/7e75f55c86c24028915f804d2b160b4e777f8107.html
實驗課代碼
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXN 50
//問題表示
int n=3,W=30;
vector<int> w;//={0,16,15,15}; //重量，下标0不用
vector<int> v;//={0,45,25,25}; //價值，下标0不用
//求解結果表示
int maxv=-9999; //存放最大價值,初始為最小值
int bestx[MAXN]; //存放最優解,全局變量
int total=1; //解空間中結點數累計,全局變量
// # 貪心法----非0/1背包問題，而是部分背包問題
// 使用n,W,w[],v[]
struct NodeType_Knap
{
double w;
double v;
double p; //p=v/w
bool operator<(const NodeType_Knap &s) const
{
return p>s.p; //按p遞減排序
}
};
vector<NodeType_Knap> A; // 含有輸入的資料和排序後的資料
double V = 0; // 價值，之前是int型，在這裡為double
double x[MAXN]; // 最優解double類型，可以選擇部分，即一定的比例
/*
* 求機關重量的價值->按照自定義的格式排序->調用 Knap
*/
void knap_m();
/*
* 排序後則貪心循環選擇，如果剩餘的容量還能容納目前的，則放進去，不能的話跳出循環，選擇部分放入
*/
void Knap();
// !# 貪心法
// # 動态規劃法
// 使用n,W,w[],v[],maxv,bestv[]
// 動态規劃數組
int dp[MAXN][MAXN];
/*
* 根據狀态轉移方程來構造動态
* 1>兩個邊界條件
* 2>由于動态規劃數組為二維數組，則兩層for循環裡判斷是否擴充活動節點
擴充則dp[i][r]=dp[i-1][r];
不擴充則二者求最大
*/
void dp_Knap();
/*
* 動态規劃數組已經填充完畢，逆着推出最優解
根據狀态轉移方程中的條件，判斷每個物品是否選擇
*/
void buildx();
// !# 動态規劃法
int main()
{
// 輸入格式
/*
3 n個物品假設為3
16 45 第一個物品的重量和價值
15 25 第二個物品的重量和價值
15 25 第三個物品的重量和價值
30 背包容量W
*/
cin >> n;
int m,l;
// 下表0不用，填充0
w.push_back(0);
v.push_back(0);
for (int j = 1; j <= n;j++)
{
cin >> m >> l;
w.push_back(m);
v.push_back(l);
}
cin >> W;
// # 貪心法
//knap_m();
// !# 貪心法
// # 動态規劃法
dp_Knap();
buildx();
// !# 動态規劃法
cout << "最優解：";
for (int i = 1;i <= n;i++)
{
if (V > 0)
{// 貪心法 輸出的是double類型
cout << x[i] << " ";
}else
{// 動态規劃輸出的是int型
cout << bestx[i] << " ";
}
}
if (V > 0)
{// 貪心法 輸出的是double類型
cout << endl << "最大價值為：" << V << endl;
}else
{// 動态規劃輸出的是int型
cout << endl << "最大價值為：" << maxv << endl;
}
return 0;
}
// 貪心法
void knap_m()
{
int i;
for ( i=0;i<=n;i++)
{
NodeType_Knap k;
k.w = w[i];
k.v = v[i];
A.push_back(k);
}
for ( i=1;i<=n;i++) //求v/w
A[i].p=A[i].v/A[i].w;
// sort(++A.begin(),A.end()); //A[1..n]排序
sort(A.begin(),A.end()); //A[1..n]排序
Knap();
}
// 求解背包問題并傳回總價值
void Knap()
{
V=0; //V初始化為0
double weight=W; //背包中能裝入的餘下重量
int i=1;
while (A[i].w < weight) //物品i能夠全部裝入時循環
{
x[i]=1; //裝入物品i
weight -= A[i].w; //減少背包中能裝入的餘下重量
V += A[i].v; //累計總價值
i++; //繼續循環
}
if (weight > 0) //當餘下重量大于0
{
x[i] = weight / A[i].w; //将物品i的一部分裝入
V += x[i] * A[i].v; //累計總價值
}
}
// 動态規劃法
void dp_Knap()
{
int i,r;
for(i = 0;i <= n;i++) //置邊界條件dp[i][0]=0
dp[i][0] = 0;
for (r = 0;r <= W;r++) //置邊界條件dp[0][r]=0
dp[0][r] = 0;
for (i = 1;i <= n;i++)
{
for (r = 1;r <= W;r++)
if (r < w[i])
dp[i][r] = dp[i-1][r];
else
if ((dp[i-1][r])>(dp[i-1][r-w[i]]+v[i]))
dp[i][r] = dp[i-1][r];
else
dp[i][r] = dp[i-1][r-w[i]]+v[i];
}
}
void buildx()
{
int i=n,r=W;
maxv=0;
while (i>=0) //判斷每個物品
{
if (dp[i][r] != dp[i-1][r])
{
bestx[i] = 1; //選取物品i
maxv += v[i]; //累計總價值
r = r - w[i];
}
else
bestx[i]=0; //不選取物品i
i--;
}
}
貪心法
不過可以運作
原文連結
https://blog.csdn.net/qq_43717119/article/details/109332899?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160752507419724827626752%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=160752507419724827626752&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allfirst_rank_v2~rank_v29-3-109332899.pc_search_result_no_baidu_js&utm_term=%E5%81%87%E8%AE%BE%E4%B8%80%E4%B8%AA0%201%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E6%98%AFn&3%EF%BC%8C%E9%87%8D%E9%87%8F%E4%B8%BAw=%EF%BC%8816,15,15%EF%BC%89%EF%BC%8C%E4%BB%B7%E5%80%BC%E4%B8%BAv&(45,25,25),%E8%83%8C%E5%8C%85%E9%99%90%E9%87%8D%E4%B8%BAW=30%EF%BC%8C%E6%B1%82%E6%94%BE%E5%85%A5%E8%83%8C%E5%8C%85%E6%80%BB%E9%87%8D%E9%87%8F%E5%B0%8F%E4%BA%8E%E7%AD%89%E4%BA%8EW%E5%B9%B6%E4%B8%94%E4%BB%B7%E5%80%BC%E6%9C%80%E5%A4%A7%E7%9A%84%E8%A7%A3%EF%BC%8C%E8%AE%BE%E8%A7%A3%E5%90%91%E9%87%8F%E4%B8%BAx&spm=1018.2118.3001.4449
0－1背包問題（回溯法解決）
#include<iostream>
#include<algorithm>
using namespace std;
#define NUM 100
int c; //背包的容量
int n; //物品的數量
int cw; //目前背包内物品的重量
int cv; //目前背包内物品的總價值
int bestv; //目前最優價值
//描述每個物品的資料結構
struct Object
{
public:
int w; //物品的重量
int v; //物品的價值
double d; //物品的機關價值
public:
double getd()
{
return d;
}
}; //物品數組
Object Q[NUM];
void backtrack(int i);
int Bound(int i);
bool cmp(Object, Object);
//物品的機關價值重量比是在輸入資料時計算的
//int main()
void main()
{
cin >> c >> n;
for (int i = 0; i < n; i++)
{
//物品的機關價值重量比是在輸入資料時計算的
// scanf_s("%d%d", &Q[i].w, &Q[i].v);
scanf("%d %d", &Q[i].w, &Q[i].v);
Q[i].d = 1.0 * Q[i].v / Q[i].w;
}
sort函數第三個參數采用預設從小到大 ,C++内置函數
sort(Q, Q + n, cmp);
//for ( i = 0; i < n; i++)
//cout << Q[i];
backtrack(1);
cout << bestv;
}
//以物品機關價值重量比遞減排序的因子：
bool cmp(Object a, Object b)
{
if (a.d>= b.d)
return true;
else
return false;
}
void backtrack(int i)
{
//到達葉子節點時更新最優值
if (i + 1 > n)
{
bestv = cv;
return;
}
//進入左子樹搜尋
if (cw + Q[i].w <= c)
{
cw += Q[i].w;
cv += Q[i].v;
backtrack(i + 1);
cw -= Q[i].w;
cv -= Q[i].v;
}
//進入右子樹搜尋
if (Bound(i + 1) > bestv)
backtrack(i + 1);
}
int Bound(int i)
{
int cleft = c - cw; //背包剩餘的容量
int b = cv; //上界
//盡量裝滿背包
while (i < n && Q[i].w <= cleft)
{
cleft -= Q[i].w;
b += Q[i].v;
i++;
}
//剩餘的部分空間也裝滿
if (i < n)
b += 1.0 * cleft * Q[i].v / Q[i].w;
return b;
}
實驗課用
方法一：
0-1背包的裸題，那就可以直接寫一個01背包的動态轉移方程：dp[j]=max(dp[j],dp[j-w[i]]+p[i])。dp[j]的意思是：當背包已裝j的重量的物品時的最大價值。那麼它可以由背包已裝j-w[i]時最大的價值進行轉移，即由dp[j-w[i]]+p[i]得到。注意每一次要将dp[]設定為0，因為背包此時無價值。當狀态方程枚舉結束後，我們再從 dp[]數組中找一遍，求得答案maxx=max{dp[i]}(i from 0 to c)，輸出答案maxx。這種動态規劃的方法的時間複雜度為O(n^2).
ps：0-1背包也可以寫成二維dp[][]，隻是這樣寫成滾動數組可以更加節省空間。
代碼：
#include<algorithm>
using namespace std;
const int maxn= 2000+50;
int n,c,w[maxn],dp[maxn],p[maxn];
int main(){
int i,j;
while(1){
scanf("%d %d",&n,&c);
if(n==0&&c==0)break;
for(i=1;i<=n;i++)cin>>w[i];
for(i=1;i<=n;i++)cin>>p[i];
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++){
for(j=c;j>=1;j--){
if(j-w[i]>=0&&dp[j]<dp[j-w[i]]+p[i]){
dp[j]=dp[j-w[i]]+p[i];
}
}
}
int maxx=0;
for(i=0;i<=c;i++)
if(maxx<dp[i])
maxx=dp[i];
cout<<maxx<<endl;
}
return 0;
}
方法二：
除了直接寫0-1背包的動态轉移方程，還可以直接寫dfs，每一個背包無非就是取和不取兩個狀态，如果要取則要求背包容量 res>=w[now]。分别用ans1，ans2表示取目前物品，不取目前物品的最大價值，dfs傳回max(ans1,ans2)，dfs的終止條件是now ==n+1。時間複雜度(2^n)。
ps:方法二相較于方法一思維上更加簡單，容易想到，但是代碼就相對麻煩，并且時間複雜度不夠優秀，當然如果加上記憶化搜尋後時間複雜度和動态規劃是相當的。我個人更喜歡方法一。
代碼：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn= 2000+50;
int n,c,w[maxn],p[maxn];
int dfs(int now,int res){
if(now==n+1)return 0;
int ans1=0,ans2=0;
if(res>=w[now]){
ans1=dfs(now+1,res-w[now])+p[now];
}
ans2=dfs(now+1,res);
if(ans1>=ans2)return ans1;
return ans2;
}
int main(){
int i,j;
while(1){
scanf("%d %d",&n,&c);
if(n==0&&c==0)break;
for(i=1;i<=n;i++)cin>>w[i];
for(i=1;i<=n;i++)cin>>p[i];
cout<<dfs(1,c)<<endl;
}
return 0;
}
參考網址
http://phoenix-zh.cn/2020/10/29/NOJ-%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E7%90%86%E8%AE%BA%E4%BD%9C%E4%B8%9A/#3-0-1%E8%83%8C%E5%8C%85