回溯演算法代碼
A. 分別用回溯法和動態規劃求0/1背包問題（c語言代碼）
#include <stdio.h>
#include <malloc.h>
#include <windows.h>typedef struct goods
{
double *value; //價值
double *weight; //重量
char *select; //是否選中到方案
int num;//物品數量
double limitw; //限制重量
}GOODS;
double maxvalue,totalvalue;//方案最大價值,物品總價值
char *select1; //臨時數組
void backpack(GOODS *g, int i, double tw, double tv)//參數為物品i,當前選擇已經達到的重量和tw,本方案可能達到的總價值
{
int k;
if (tw + g->weight[i] <= g->limitw)//將物品i包含在當前方案,且重量小於等於限制重量
{
select1[i] = 1; //選中第i個物品
if (i < g->num - 1) //若物品i不是最後一個物品
backpack(g, i + 1, tw + g->weight[i], tv); //遞歸調用,繼續添加下一物品
else //若已到最後一個物品
{
for (k = 0; k < g->num; ++k) //將狀態標志復制到option數組中
g->select[k] = select1[k];
maxvalue = tv; //保存當前方案的最大價值
}
}
select1[i] = 0; //取消物品i的選擇狀態
if (tv - g->value[i] > maxvalue)//若物品總價值減去物品i的價值還大於maxv方案中已有的價值,說明還可以繼續向方案中添加物品
{
if (i < g->num - 1) //若物品i不是最後一個物品
backpack(g, i + 1, tw, tv - g->value[i]); //遞歸調用,繼續加入下一物品
else //若已到最後一個物品
{
for (k = 0; k < g->num; ++k) //將狀態標志復制到option數組中
g->select[k] = select1[k];
maxvalue = tv - g->value[i]; //保存當前方案的最大價值(從物品總價值中減去物品i的價值)
}
}
}
int main()
{
double sumweight;
GOODS g;
int i;
printf("背包最大重量:");
scanf("%lf",&g.limitw);
printf("可選物品數量:");
scanf("%d",&g.num);
if(!(g.value = (double *)malloc(sizeof(double)*g.num)))//分配內存保存物品價值
{
printf("內存分配失敗\n");
exit(0);
}
if(!(g.weight = (double *)malloc(sizeof(double)*g.num)))//分配內存保存物品的重量
{
printf("內存分配失敗\n");
exit(0);
}
if(!(g.select = (char *)malloc(sizeof(char)*g.num)))//分配內存保存物品的重量
{
printf("內存分配失敗\n");
exit(0);
}
if(!(select1 = (char *)malloc(sizeof(char)*g.num)))//分配內存保存物品的重量
{
printf("內存分配失敗\n");
exit(0);
}
totalvalue=0;
for (i = 0; i < g.num; i++)
{
printf("輸入第%d號物品的重量和價值:",i + 1);
scanf("%lf%lf",&g.weight[i],&g.value[i]);
totalvalue+=g.value[i];//統計所有物品的價值總和
}
printf("\n背包最大能裝的重量為:%.2f\n\n",g.limitw);
for (i = 0; i < g.num; i++)
printf("第%d號物品重:%.2f,價值:%.2f\n", i + 1, g.weight[i], g.value[i]);
for (i = 0; i < g.num; i++)//初始設各物品都沒加入選擇集
select1[i]=0;
maxvalue=0;//加入方案物品的總價值
backpack(&g,0,0.0,totalvalue); //第0號物品加入方案,總重量為0,所有物品價值為totalvalue
sumweight=0;
printf("\n可將以下物品裝入背包,使背包裝的物品價值最大:\n");
for (i = 0; i < g.num; ++i)
if (g.select[i])
{
printf("第%d號物品,重量:%.2f,價值:%.2f\n", i + 1, g.weight[i], g.value[i]);
sumweight+=g.weight[i];
}
printf("\n總重量為: %.2f,總價值為:%.2f\n", sumweight, maxvalue );
// getch();
return 0;
}
B. 求教C語言回溯法寫出八皇後問題的92種解
(1)全排列
將自然數1~n進行排列，共形成n!中排列方式，叫做全排列。
例如3的全排列是：1/2/3、1/3/2、2/1/3、2/3/1、3/1/2、3/2/1，共3!=6種。
(2)8皇後（或者n皇後）
保證8個皇後不能互相攻擊，即保證每一橫行、每一豎行、每一斜行最多一個皇後。
我們撇開第三個條件，如果每一橫行、每一豎行都只有一個皇後。
將8*8棋盤標上坐標。我們討論其中的一種解法：
- - - - - - - Q
- - - Q - - - -
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -
如果用坐標表示就是：(1,8) (2,4) (3,1) (4,3) (5,6) (6,2) (7,7) (8,5)
將橫坐標按次序排列，縱坐標就是8/4/1/3/6/2/7/5。這就是1~8的一個全排列。
我們將1~8的全排列存入輸入a[]中(a[0]~a[7])，然後8個皇後的坐標就是(i+1,a[i])，其中i為0~7。
這樣就能保證任意兩個不會同一行、同一列了。
置於斜行，你知道的，兩個點之間連線的斜率絕對值為1或者-1即為同一斜行，充要條件是|x1-x2|=|y1-y2|（兩個點的坐標為（x1,y1）(x2,y2)）。我們在輸出的時候進行判斷，任意兩個點如果滿足上述等式，則判為失敗，不輸出。
下面附上代碼：添加必要的注釋，其中全排列的實現看看注釋應該可以看懂：
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
intprinted;
//該函數用於畫圖，這里為了節約空間則略去
//讀者只需要將draw(a,k);去掉注釋即可畫圖
voiddraw(int*a,intk)
{
inti,j;
for(i=0;i<k;i++)
{
printf(" ");
for(j=0;j<k;j++)
//有皇後輸出Q，否則輸出-
if(a[i]-1==j)printf("Q");elseprintf("-");
printf(" ");
}
printf(" ");
}
//遞歸實現全排列,a是數組，iStep是位置的測試點，k是皇後的個數，一般等於8
voidSettle(int*a,intiStep,intk)
{
inti,j,l,flag=1;
//如果iStep的數字等於a之前的數字，則存在重復，返回
for(i=0;i<iStep-1;i++)
if(a[iStep-1]==a[i])return;
//如果iStep==k，即遞歸結束到最後一位，可以驗證是否斜行滿足
if(iStep==k)
{
//雙重循環判斷是否斜行滿足
for(j=0;j<k;j++)
for(l=0;l<k&&l!=j;l++)
//如果不滿足，則flag=0
if(fabs(j-l)==fabs(a[j]-a[l]))flag=0;
//如果flag==1，則通過了斜行的所有測試，輸出。
if(flag)
{
for(i=0;i<k;i++)
printf("(%d,%d)",i+1,a[i]);
printf(" ");
//如果去掉這里的注釋可以獲得畫圖，由於空間不夠，這里略去
// draw(a,k);
//printed變數計算有多少滿足題意的結果，是全局變數
printed++;
}
flag=1;
}
//如果未測試至最後末尾，則測試下一位（遞歸）
for(i=1;i<=k;i++)
{
a[iStep]=i;
Settle(a,iStep+1,k);
}
}
voidmain()
{
int*a;
intk;
//輸入維數，建立數組
printf("Enterthesizeofthesquare:");
scanf("%d",&k);
a=(int*)calloc(k,sizeof(int));
//清屏，從iStep=0處進入遞歸
system("cls");
Settle(a,0,k);
//判斷最後是否有結果
if(!printed)printf("Noanswersaccepted! ");
elseprintf("%dstatesavailable! ",printed);
}
附輸出結果（輸入k=8）：
(1,1)(2,5)(3,8)(4,6)(5,3)(6,7)(7,2)(8,4)
(1,1)(2,6)(3,8)(4,3)(5,7)(6,4)(7,2)(8,5)
(1,1)(2,7)(3,4)(4,6)(5,8)(6,2)(7,5)(8,3)
(1,1)(2,7)(3,5)(4,8)(5,2)(6,4)(7,6)(8,3)
(1,2)(2,4)(3,6)(4,8)(5,3)(6,1)(7,7)(8,5)
(1,2)(2,5)(3,7)(4,1)(5,3)(6,8)(7,6)(8,4)
(1,2)(2,5)(3,7)(4,4)(5,1)(6,8)(7,6)(8,3)
(1,2)(2,6)(3,1)(4,7)(5,4)(6,8)(7,3)(8,5)
(1,2)(2,6)(3,8)(4,3)(5,1)(6,4)(7,7)(8,5)
(1,2)(2,7)(3,3)(4,6)(5,8)(6,5)(7,1)(8,4)
(1,2)(2,7)(3,5)(4,8)(5,1)(6,4)(7,6)(8,3)
(1,2)(2,8)(3,6)(4,1)(5,3)(6,5)(7,7)(8,4)
(1,3)(2,1)(3,7)(4,5)(5,8)(6,2)(7,4)(8,6)
(1,3)(2,5)(3,2)(4,8)(5,1)(6,7)(7,4)(8,6)
(1,3)(2,5)(3,2)(4,8)(5,6)(6,4)(7,7)(8,1)
(1,3)(2,5)(3,7)(4,1)(5,4)(6,2)(7,8)(8,6)
(1,3)(2,5)(3,8)(4,4)(5,1)(6,7)(7,2)(8,6)
(1,3)(2,6)(3,2)(4,5)(5,8)(6,1)(7,7)(8,4)
(1,3)(2,6)(3,2)(4,7)(5,1)(6,4)(7,8)(8,5)
(1,3)(2,6)(3,2)(4,7)(5,5)(6,1)(7,8)(8,4)
(1,3)(2,6)(3,4)(4,1)(5,8)(6,5)(7,7)(8,2)
(1,3)(2,6)(3,4)(4,2)(5,8)(6,5)(7,7)(8,1)
(1,3)(2,6)(3,8)(4,1)(5,4)(6,7)(7,5)(8,2)
(1,3)(2,6)(3,8)(4,1)(5,5)(6,7)(7,2)(8,4)
(1,3)(2,6)(3,8)(4,2)(5,4)(6,1)(7,7)(8,5)
(1,3)(2,7)(3,2)(4,8)(5,5)(6,1)(7,4)(8,6)
(1,3)(2,7)(3,2)(4,8)(5,6)(6,4)(7,1)(8,5)
(1,3)(2,8)(3,4)(4,7)(5,1)(6,6)(7,2)(8,5)
(1,4)(2,1)(3,5)(4,8)(5,2)(6,7)(7,3)(8,6)
(1,4)(2,1)(3,5)(4,8)(5,6)(6,3)(7,7)(8,2)
(1,4)(2,2)(3,5)(4,8)(5,6)(6,1)(7,3)(8,7)
(1,4)(2,2)(3,7)(4,3)(5,6)(6,8)(7,1)(8,5)
(1,4)(2,2)(3,7)(4,3)(5,6)(6,8)(7,5)(8,1)
(1,4)(2,2)(3,7)(4,5)(5,1)(6,8)(7,6)(8,3)
(1,4)(2,2)(3,8)(4,5)(5,7)(6,1)(7,3)(8,6)
(1,4)(2,2)(3,8)(4,6)(5,1)(6,3)(7,5)(8,7)
(1,4)(2,6)(3,1)(4,5)(5,2)(6,8)(7,3)(8,7)
(1,4)(2,6)(3,8)(4,2)(5,7)(6,1)(7,3)(8,5)
(1,4)(2,6)(3,8)(4,3)(5,1)(6,7)(7,5)(8,2)
(1,4)(2,7)(3,1)(4,8)(5,5)(6,2)(7,6)(8,3)
(1,4)(2,7)(3,3)(4,8)(5,2)(6,5)(7,1)(8,6)
(1,4)(2,7)(3,5)(4,2)(5,6)(6,1)(7,3)(8,8)
(1,4)(2,7)(3,5)(4,3)(5,1)(6,6)(7,8)(8,2)
(1,4)(2,8)(3,1)(4,3)(5,6)(6,2)(7,7)(8,5)
(1,4)(2,8)(3,1)(4,5)(5,7)(6,2)(7,6)(8,3)
(1,4)(2,8)(3,5)(4,3)(5,1)(6,7)(7,2)(8,6)
(1,5)(2,1)(3,4)(4,6)(5,8)(6,2)(7,7)(8,3)
(1,5)(2,1)(3,8)(4,4)(5,2)(6,7)(7,3)(8,6)
(1,5)(2,1)(3,8)(4,6)(5,3)(6,7)(7,2)(8,4)
(1,5)(2,2)(3,4)(4,6)(5,8)(6,3)(7,1)(8,7)
(1,5)(2,2)(3,4)(4,7)(5,3)(6,8)(7,6)(8,1)
(1,5)(2,2)(3,6)(4,1)(5,7)(6,4)(7,8)(8,3)
(1,5)(2,2)(3,8)(4,1)(5,4)(6,7)(7,3)(8,6)
(1,5)(2,3)(3,1)(4,6)(5,8)(6,2)(7,4)(8,7)
(1,5)(2,3)(3,1)(4,7)(5,2)(6,8)(7,6)(8,4)
(1,5)(2,3)(3,8)(4,4)(5,7)(6,1)(7,6)(8,2)
(1,5)(2,7)(3,1)(4,3)(5,8)(6,6)(7,4)(8,2)
(1,5)(2,7)(3,1)(4,4)(5,2)(6,8)(7,6)(8,3)
(1,5)(2,7)(3,2)(4,4)(5,8)(6,1)(7,3)(8,6)
(1,5)(2,7)(3,2)(4,6)(5,3)(6,1)(7,4)(8,8)
(1,5)(2,7)(3,2)(4,6)(5,3)(6,1)(7,8)(8,4)
(1,5)(2,7)(3,4)(4,1)(5,3)(6,8)(7,6)(8,2)
(1,5)(2,8)(3,4)(4,1)(5,3)(6,6)(7,2)(8,7)
(1,5)(2,8)(3,4)(4,1)(5,7)(6,2)(7,6)(8,3)
(1,6)(2,1)(3,5)(4,2)(5,8)(6,3)(7,7)(8,4)
(1,6)(2,2)(3,7)(4,1)(5,3)(6,5)(7,8)(8,4)
(1,6)(2,2)(3,7)(4,1)(5,4)(6,8)(7,5)(8,3)
(1,6)(2,3)(3,1)(4,7)(5,5)(6,8)(7,2)(8,4)
(1,6)(2,3)(3,1)(4,8)(5,4)(6,2)(7,7)(8,5)
(1,6)(2,3)(3,1)(4,8)(5,5)(6,2)(7,4)(8,7)
(1,6)(2,3)(3,5)(4,7)(5,1)(6,4)(7,2)(8,8)
(1,6)(2,3)(3,5)(4,8)(5,1)(6,4)(7,2)(8,7)
(1,6)(2,3)(3,7)(4,2)(5,4)(6,8)(7,1)(8,5)
(1,6)(2,3)(3,7)(4,2)(5,8)(6,5)(7,1)(8,4)
(1,6)(2,3)(3,7)(4,4)(5,1)(6,8)(7,2)(8,5)
(1,6)(2,4)(3,1)(4,5)(5,8)(6,2)(7,7)(8,3)
(1,6)(2,4)(3,2)(4,8)(5,5)(6,7)(7,1)(8,3)
(1,6)(2,4)(3,7)(4,1)(5,3)(6,5)(7,2)(8,8)
(1,6)(2,4)(3,7)(4,1)(5,8)(6,2)(7,5)(8,3)
(1,6)(2,8)(3,2)(4,4)(5,1)(6,7)(7,5)(8,3)
(1,7)(2,1)(3,3)(4,8)(5,6)(6,4)(7,2)(8,5)
(1,7)(2,2)(3,4)(4,1)(5,8)(6,5)(7,3)(8,6)
(1,7)(2,2)(3,6)(4,3)(5,1)(6,4)(7,8)(8,5)
(1,7)(2,3)(3,1)(4,6)(5,8)(6,5)(7,2)(8,4)
(1,7)(2,3)(3,8)(4,2)(5,5)(6,1)(7,6)(8,4)
(1,7)(2,4)(3,2)(4,5)(5,8)(6,1)(7,3)(8,6)
(1,7)(2,4)(3,2)(4,8)(5,6)(6,1)(7,3)(8,5)
(1,7)(2,5)(3,3)(4,1)(5,6)(6,8)(7,2)(8,4)
(1,8)(2,2)(3,4)(4,1)(5,7)(6,5)(7,3)(8,6)
(1,8)(2,2)(3,5)(4,3)(5,1)(6,7)(7,4)(8,6)
(1,8)(2,3)(3,1)(4,6)(5,2)(6,5)(7,7)(8,4)
(1,8)(2,4)(3,1)(4,3)(5,6)(6,2)(7,7)(8,5)
92statesavailable!
C. c語言回溯演算法
if(n==7||a[n+1][i]!=1&&a[n+1][i+1]!=1&&a[n+1][i-1]!=1)
這行的代碼是判斷是否可以放皇後的句子。如果可以就將所在位置置 1 。後面也就是這樣做判斷的。這個程序應當有問題，其中try應當是C語言中一個關鍵字啊，不可以這么用。
就我的看法：八皇後的問題應當用遞歸加回溯會都到更好的代碼，我寫過，不過也快忘了。
D. java或者C/C++怎麼用回溯法解決最小長度電路板排列問題
以java為例，希望能夠幫到你。
電路板排列問題
問題描述
將n塊電路板以最佳排列方式插入帶有n個插槽的機箱中。n塊電路板的不同排列方式對應於不同的電路板插入方案。設B={1, 2, …, n}是n塊電路板的集合，L={N1, N2, …, Nm}是連接這n塊電路板中若干電路板的m個連接塊。Ni是B的一個子集，且Ni中的電路板用同一條導線連接在一起。設x表示n塊電路板的一個排列，即在機箱的第i個插槽中插入的電路板編號是x[i]。x所確定的電路板排列Density (x)密度定義為跨越相鄰電路板插槽的最大連線數。
例：如圖，設n=8, m=5，給定n塊電路板及其m個連接塊：B={1, 2, 3, 4, 5, 6, 7, 8}，N1={4, 5, 6}，N2={2, 3}，N3={1, 3}，N4={3, 6}，N5={7, 8};其中兩個可能的排列如圖所示，則該電路板排列的密度分別是2，3。
E. 急需C++代碼！作業分配（回溯法）
回溯搜索的非遞歸思路及實例源碼，這是一個通用框架！
http://hi..com/gropefor/blog/item/5d2636542b36e6ccb745ae34.html
F. 硬幣兌換問題回溯法偽代碼
A數組用來存放硬幣,數值1代表正面，0代表反面；
static int s;s是存放每列狀態的數初始為0代表一列都沒翻，第幾位為1就代表第幾列被翻轉
int turncoin(A,S,N，n) //A(N*9數組） ，N是行數 n代表當次翻哪一列 初次調用n=0，代表第一列
{ int i=1;//因為每列只有兩種狀態，所以每列只翻一次
static int max=0;//用來存放翻轉後正面朝上的最大硬幣數；
static int S;//大S用來存儲當前硬幣堆的翻轉狀態
do {turncoin(A,S,N，n+1);if （n==8）{ int tem=sum //sum為遍歷A數組,所有元素之和（即為當前正面朝上的硬幣數)
if（sum>max）{S=s; //把當前翻轉狀態存儲到S,S內總是存儲著擁有正面朝上硬幣數量最高的一種翻轉狀態；}}}while(i--&&transform(N，n));
//transform()函數翻轉第N列的硬幣 並且對s的第n位置一 成功返回ture 並且對是 實現就是for(i=0；
i
拓展資料：
一、題目描述：
一個翻硬幣的游戲，有N(N <=10000）行硬幣，每行有九個硬幣，排成一個N*9的方陣，有的硬幣正面朝上，有的反面朝上。我們每次可把一整行或者一整列的所有硬幣翻過來，請問怎麼翻，使得正面朝上的硬幣盡量多（翻硬幣無次數限制）。
二、思路分析：
枚舉2^9種列的翻法。
遍歷N行，如果某行正面朝上的少，翻之；如果正面朝上的多，不翻
記下使得正面最多的方法即可
耗時O(2^9 * N)
這個得到的是最優解.用位運算效率還是很高的.
對每一列,都用一個9位的數表示,一共有N個
然後便利所有的9位狀態,(000000000)-(111111111) (二進制)
對於每個狀態,都與這N個數異或,每次異或後累加所有的1的值假設為k,如果k小於5則k=9-k.
對N個數累加所有的k,得到最終累加和.
求出所有狀態下累加和最大的,就是正面朝上的硬幣盡量多的個數.
翻面的方法橫列分別是最優解的8位狀態和與之對應的每個數異或後累加和k是否小於5.
G. 回溯演算法 求1-20這2個數擺成環，要求相鄰的兩個數的和是素數。我的代碼如下：沒有語法錯誤，但是死循環
intsearch(int)、intprint()、intmain()這三個函數名前都有返回值類型符，但函數體內卻都沒有返回語句。你也寫復雜了，下面的代碼就可以了：
#include"stdio.h"
intprime(intn){
inti;
if(n>2&&!(n&1)||n<2)
return0;
for(i=3;i*i<=n;i+=2)
if(!(n%i))
return0;
return1;
}
intmain(void){
inti,j;
for(i=1;i<20;i++)
if(prime(j=(i<<1)+1))
printf("%2d+%2d=%2d ",i,i+1,j);
return0;
}
H. 0-1背包問題的多種解法代碼（動態規劃、貪心法、回溯法、分支限界法）
一.動態規劃求解0-1背包問題
/************************************************************************/
/* 0-1背包問題：
/* 給定n種物品和一個背包
/* 物品i的重量為wi，其價值為vi
/* 背包的容量為c
/* 應如何選擇裝入背包的物品，使得裝入背包中的物品
/* 的總價值最大？
/* 註：在選擇裝入背包的物品時，對物品i只有兩種選擇，
/* 即裝入或不裝入背包。不能將物品i裝入多次，也
/* 不能只裝入部分的物品i。
/*
/* 1. 0-1背包問題的形式化描述：
/* 給定c>0, wi>0, vi>0, 0<=i<=n，要求找到一個n元的
/* 0-1向量(x1, x2, ..., xn), 使得：
/* max sum_{i=1 to n} (vi*xi),且滿足如下約束：
/* (1) sum_{i=1 to n} (wi*xi) <= c
/* (2) xi∈{0, 1}, 1<=i<=n
/*
/* 2. 0-1背包問題的求解
/* 0-1背包問題具有最優子結構性質和子問題重疊性質，適於
/* 採用動態規劃方法求解
/*
/* 2.1 最優子結構性質
/* 設(y1,y2,...,yn)是給定0-1背包問題的一個最優解，則必有
/* 結論，(y2,y3,...,yn)是如下子問題的一個最優解：
/* max sum_{i=2 to n} (vi*xi)
/* (1) sum_{i=2 to n} (wi*xi) <= c - w1*y1
/* (2) xi∈{0, 1}, 2<=i<=n
/* 因為如若不然，則該子問題存在一個最優解(z2,z3,...,zn)，
/* 而(y2,y3,...,yn)不是其最優解。那麼有：
/* sum_{i=2 to n} (vi*zi) > sum_{i=2 to n} (vi*yi)
/* 且，w1*y1 + sum_{i=2 to n} (wi*zi) <= c
/* 進一步有：
/* v1*y1 + sum_{i=2 to n} (vi*zi) > sum_{i=1 to n} (vi*yi)
/* w1*y1 + sum_{i=2 to n} (wi*zi) <= c
/* 這說明：(y1,z2,z3,...zn)是所給0-1背包問題的更優解，那麼
/* 說明(y1,y2,...,yn)不是問題的最優解，與前提矛盾，所以最優
/* 子結構性質成立。
/*
/* 2.2 子問題重疊性質
/* 設所給0-1背包問題的子問題 P(i,j)為：
/* max sum_{k=i to n} (vk*xk)
/* (1) sum_{k=i to n} (wk*xk) <= j
/* (2) xk∈{0, 1}, i<=k<=n
/* 問題P(i,j)是背包容量為j、可選物品為i,i+1,...,n時的子問題
/* 設m(i,j)是子問題P(i,j)的最優值，即最大總價值。則根據最優
/* 子結構性質，可以建立m(i,j)的遞歸式：
/* a. 遞歸初始 m(n,j)
/* //背包容量為j、可選物品只有n，若背包容量j大於物品n的
/* //重量，則直接裝入；否則無法裝入。
/* m(n,j) = vn, j>=wn
/* m(n,j) = 0, 0<=j<wn
/* b. 遞歸式 m(i,j)
/* //背包容量為j、可選物品為i,i+1,...,n
/* //如果背包容量j<wi，則根本裝不進物品i，所以有：
/* m(i,j) = m(i+1,j), 0<=j<wi
/* //如果j>=wi，則在不裝物品i和裝入物品i之間做出選擇
/* 不裝物品i的最優值：m(i+1,j)
/* 裝入物品i的最優值：m(i+1, j-wi) + vi
/* 所以：
/* m(i,j) = max {m(i+1,j), m(i+1, j-wi) + vi}, j>=wi
/*
/************************************************************************/
#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))
template <typename Type>
void Knapsack(Type* v, int *w, int c, int n, Type **m)
{
//遞歸初始條件
int jMax = min(w[n] - 1, c);
for (int j=0; j<=jMax; j++) {
m[n][j] = 0;
}
for (j=w[n]; j<=c; j++) {
m[n][j] = v[n];
}
//i從2到n-1，分別對j>=wi和0<=j<wi即使m(i,j)
for (int i=n-1; i>1; i--) {
jMax = min(w[i] - 1, c);
for (int j=0; j<=jMax; j++) {
m[i][j] = m[i+1][j];
}
for (j=w[i]; j<=c; j++) {
m[i][j] = max(m[i+1][j], m[i+1][j-w[i]]+v[i]);
}
}
m[1][c] = m[2][c];
if (c >= w[1]) {
m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]);
}
}
template <typename Type>
void TraceBack(Type **m, int *w, int c, int n, int* x)
{
for (int i=1; i<n; i++) {
if(m[i][c] == m[i+1][c]) x[i] = 0;
else {
x[i] = 1;
c -= w[i];
}
}
x[n] = (m[n][c])? 1:0;
}
int main(int argc, char* argv[])
{
int n = 5;
int w[6] = {-1, 2, 2, 6, 5, 4};
int v[6] = {-1, 6, 3, 5, 4, 6};
int c = 10;
int **ppm = new int*[n+1];
for (int i=0; i<n+1; i++) {
ppm[i] = new int[c+1];
}
int x[6];
Knapsack<int>(v, w, c, n, ppm);
TraceBack<int>(ppm, w, c, n, x);
return 0;
}
二.貪心演算法求解0-1背包問題
1.貪心法的基本思路：
——從問題的某一個初始解出發逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某演算法中的某一步不能再繼續前進時，演算法停止。
該演算法存在問題：
1).不能保證求得的最後解是最佳的；
2).不能用來求最大或最小解問題；
3).只能求滿足某些約束條件的可行解的范圍。
實現該演算法的過程：
從問題的某一初始解出發；
while 能朝給定總目標前進一步 do
求出可行解的一個解元素；
由所有解元素組合成問題的一個可行解；
2.例題分析
1).[背包問題]有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。
要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
價值 10 40 30 50 35 40 30
分析：
目標函數： ∑pi最大
約束條件是裝入的物品總重量不超過背包容量：∑wi<=M( M=150)
（1）根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？
（2）每次挑選所佔空間最小的物品裝入是否能得到最優解？
（3）每次選取單位容量價值最大的物品，成為解本題的策略。
<程序代碼:>(環境:c++)
#include<iostream.h>
#define max 100 //最多物品數
void sort (int n,float a[max],float b[max]) //按價值密度排序
{
int j,h,k;
float t1,t2,t3,c[max];
for(k=1;k<=n;k++)
c[k]=a[k]/b[k];
for(h=1;h<n;h++)
for(j=1;j<=n-h;j++)
if(c[j]<c[j+1])
{t1=a[j];a[j]=a[j+1];a[j+1]=t1;
t2=b[j];b[j]=b[j+1];b[j+1]=t2;
t3=c[j];c[j]=c[j+1];c[j+1]=t3;
}
}
void knapsack(int n,float limitw,float v[max],float w[max],int x[max])
{float c1; //c1為背包剩餘可裝載重量
int i;
sort(n,v,w); //物品按價值密度排序
c1=limitw;
for(i=1;i<=n;i++)
{
if(w[i]>c1)break;
x[i]=1; //x[i]為1時，物品i在解中
c1=c1-w[i];
}
}
void main()
{int n,i,x[max];
float v[max],w[max],totalv=0,totalw=0,limitw;
cout<<"請輸入n和limitw:";
cin>>n >>limitw;
for(i=1;i<=n;i++)
x[i]=0; //物品選擇情況表初始化為0
cout<<"請依次輸入物品的價值："<<endl;
for(i=1;i<=n;i++)
cin>>v[i];
cout<<endl;
cout<<"請依次輸入物品的重量："<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<endl;
knapsack (n,limitw,v,w,x);
cout<<"the selection is:";
for(i=1;i<=n;i++)
{
cout<<x[i];
if(x[i]==1)
totalw=totalw+w[i];
}
cout<<endl;
cout<<"背包的總重量為："<<totalw<<endl; //背包所裝載總重量
cout<<"背包的總價值為："<<totalv<<endl; //背包的總價值
}
三.回溯演算法求解0-1背包問題
1.0-l背包問題是子集選取問題。
一般情況下，0-1背包問題是NP難題。0-1背包
問題的解空間可用子集樹表示。解0-1背包問題的回溯法與裝載問題的回溯法十分類
似。在搜索解空間樹時，只要其左兒子結點是一個可行結點，搜索就進入其左子樹。當
右子樹有可能包含最優解時才進入右子樹搜索。否則將右子樹剪去。設r是當前剩餘
物品價值總和；cp是當前價值；bestp是當前最優價值。當cp+r≤bestp時，可剪去右
子樹。計算右子樹中解的上界的更好方法是將剩餘物品依其單位重量價值排序，然後
依次裝入物品，直至裝不下時，再裝入該物品的一部分而裝滿背包。由此得到的價值是
右子樹中解的上界。
2.解決辦法思路：
為了便於計算上界，可先將物品依其單位重量價值從大到小排序，此後只要順序考
察各物品即可。在實現時，由bound計算當前結點處的上界。在搜索解空間樹時，只要其左兒子節點是一個可行結點，搜索就進入左子樹，在右子樹中有可能包含最優解是才進入右子樹搜索。否則將右子樹剪去。
回溯法是一個既帶有系統性又帶有跳躍性的的搜索演算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。演算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的演算法稱為回溯法，它適用於解一些組合數較大的問題。
2.演算法框架：
a.問題的解空間：應用回溯法解問題時，首先應明確定義問題的解空間。問題的解空間應到少包含問題的一個（最優）解。
b.回溯法的基本思想：確定了解空間的組織結構後，回溯法就從開始結點（根結點）出發，以深度優先的方式搜索整個解空間。這個開始結點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為一個新的活結點，並成為當前擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。換句話說，這個結點不再是一個活結點。此時，應往回移動（回溯）至最近的一個活結點處，並使這個活結點成為當前的擴展結點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止。
3.運用回溯法解題通常包含以下三個步驟：
a.針對所給問題，定義問題的解空間；
b.確定易於搜索的解空間結構；
c.以深度優先的方式搜索解空間，並且在搜索過程中用剪枝函數避免無效搜索；
#include<iostream>
using namespace std;
class Knap
{
friend int Knapsack(int p[],int w[],int c,int n );
public:
void print()
{
for(int m=1;m<=n;m++)
{
cout<<bestx[m]<<" ";
}
cout<<endl;
};
private:
int Bound(int i);
void Backtrack(int i);
int c;//背包容量
int n; //物品數
int *w;//物品重量數組
int *p;//物品價值數組
int cw;//當前重量
int cp;//當前價值
int bestp;//當前最優值
int *bestx;//當前最優解
int *x;//當前解
};
int Knap::Bound(int i)
{
//計算上界
int cleft=c-cw;//剩餘容量
int b=cp;
//以物品單位重量價值遞減序裝入物品
while(i<=n&&w[i]<=cleft)
{
cleft-=w[i];
b+=p[i];
i++;
}
//裝滿背包
if(i<=n)
b+=p[i]/w[i]*cleft;
return b;
}
void Knap::Backtrack(int i)
{
if(i>n)
{
if(bestp<cp)
{
for(int j=1;j<=n;j++)
bestx[j]=x[j];
bestp=cp;
}
return;
}
if(cw+w[i]<=c) //搜索左子樹
{
x[i]=1;
cw+=w[i];
cp+=p[i];
Backtrack(i+1);
cw-=w[i];
cp-=p[i];
}
if(Bound(i+1)>bestp)//搜索右子樹
{
x[i]=0;
Backtrack(i+1);
}
}
class Object
{
friend int Knapsack(int p[],int w[],int c,int n);
public:
int operator<=(Object a)const
{
return (d>=a.d);
}
private:
int ID;
float d;
};
int Knapsack(int p[],int w[],int c,int n)
{
//為Knap::Backtrack初始化
int W=0;
int P=0;
int i=1;
Object *Q=new Object[n];
for(i=1;i<=n;i++)
{
Q[i-1].ID=i;
Q[i-1].d=1.0*p[i]/w[i];
P+=p[i];
W+=w[i];
}
if(W<=c)
return P;//裝入所有物品
//依物品單位重量排序
float f;
for( i=0;i<n;i++)
for(int j=i;j<n;j++)
{
if(Q[i].d<Q[j].d)
{
f=Q[i].d;
Q[i].d=Q[j].d;
Q[j].d=f;
}
}
Knap K;
K.p = new int[n+1];
K.w = new int[n+1];
K.x = new int[n+1];
K.bestx = new int[n+1];
K.x[0]=0;
K.bestx[0]=0;
for( i=1;i<=n;i++)
{
K.p[i]=p[Q[i-1].ID];
K.w[i]=w[Q[i-1].ID];
}
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
//回溯搜索
K.Backtrack(1);
K.print();
delete [] Q;
delete [] K.w;
delete [] K.p;
return K.bestp;
}
void main()
{
int *p;
int *w;
int c=0;
int n=0;
int i=0;
char k;
cout<<"0-1背包問題——回溯法 "<<endl;
cout<<" by zbqplayer "<<endl;
while(k)
{
cout<<"請輸入背包容量(c)："<<endl;
cin>>c;
cout<<"請輸入物品的個數(n)："<<endl;
cin>>n;
p=new int[n+1];
w=new int[n+1];
p[0]=0;
w[0]=0;
cout<<"請輸入物品的價值(p)："<<endl;
for(i=1;i<=n;i++)
cin>>p[i];
cout<<"請輸入物品的重量(w)："<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<"最優解為(bestx)："<<endl;
cout<<"最優值為(bestp)："<<endl;
cout<<Knapsack(p,w,c,n)<<endl;
cout<<"[s] 重新開始"<<endl;
cout<<"[q] 退出"<<endl;
cin>>k;
}
四.分支限界法求解0-1背包問題
1.問題描述：已知有N個物品和一個可以容納M重量的背包，每種物品I的重量為WEIGHT，一個只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的總效益最大。
2.設計思想與分析：對物品的選取與否構成一棵解樹，左子樹表示不裝入，右表示裝入，通過檢索問題的解樹得出最優解，並用結點上界殺死不符合要求的結點。
#include <iostream.h>
struct good
{
int weight;
int benefit;
int flag;//是否可以裝入標記
};
int number=0;//物品數量
int upbound=0;
int curp=0, curw=0;//當前效益值與重量
int maxweight=0;
good *bag=NULL;
void Init_good()
{
bag=new good [number];
for(int i=0; i<number; i++)
{
cout<<"請輸入第件"<<i+1<<"物品的重量:";
cin>>bag[i].weight;
cout<<"請輸入第件"<<i+1<<"物品的效益:";
cin>>bag[i].benefit;
bag[i].flag=0;//初始標志為不裝入背包
cout<<endl;
}
}
int getbound(int num, int *bound_u)//返回本結點的c限界和u限界
{
for(int w=curw, p=curp; num<number && (w+bag[num].weight)<=maxweight; num++)
{
w=w+bag[num].weight;
p=w+bag[num].benefit;
}
*bound_u=p+bag[num].benefit;
return ( p+bag[num].benefit*((maxweight-w)/bag[num].weight) );
}
void LCbag()
{
int bound_u=0, bound_c=0;//當前結點的c限界和u限界
for(int i=0; i<number; i++)//逐層遍歷解樹決定是否裝入各個物品
{
if( ( bound_c=getbound(i+1, &bound_u) )>upbound )//遍歷左子樹
upbound=bound_u;//更改已有u限界,不更改標志
if( getbound(i, &bound_u)>bound_c )//遍歷右子樹
//若裝入，判斷右子樹的c限界是否大於左子樹根的c限界，是則裝入
{
upbound=bound_u;//更改已有u限界
curp=curp+bag[i].benefit;
curw=curw+bag[i].weight;//從已有重量和效益加上新物品
bag[i].flag=1;//標記為裝入
}
}
}
void Display()
{
cout<<"可以放入背包的物品的編號為：";
for(int i=0; i<number; i++)
if(bag[i].flag>0)
cout<<i+1<<" ";
cout<<endl;
delete []bag;
}
I. 求C++語言版用回溯法解決八皇後問題的代碼
#include <fstream>
#include <bitset>
#include <vector>
using namespace std;
ofstream cout("out.txt");
void BitSetTest()
{
const int n = 4;
for (int i = 0; i < 16; i++)
cout << bitset<4>(i) << endl;
}
class Enum
{
protected:
vector<int> A;
int M, N;
void Print()
{
for (int i = 0; i < N; i++)
cout << A[i];
cout << endl;
}
virtual bool Valid(int k) {return true;}
public:
Enum(int m, int n): M(m), N(n), A(n) {}
void Generate(int k)
{
if (k == N)
Print();
else
for (A[k] = 0; A[k] < M; A[k]++)
if (Valid(k))
Generate(k + 1);
}
void Generate()
{
int k = 0;
A[k] = -1;
while (k >= 0)
{
A[k]++;
if (A[k] == M)
k--;
else if (Valid(k))
{
if (k == N - 1)
Print();
else
A[++k] = -1;
}
}
}
};
class Perm: public Enum
{
virtual bool Valid(int k)
{
bool v = true;
for (int i = 0; v && i < k; i++)
v = A[k] != A[i];
return v;
}
public:
Perm(int n): Enum(n, n) {}
};
class nQueens: public Enum
{
virtual bool Valid(int k)
{
bool v = true;
for (int i = 0; v && i < k; i++)
v = A[k] != A[i] && k - i != abs(A[k] - A[i]);
return v;
}
public:
nQueens(int n): Enum(n, n) {}
};
int main()
{
nQueens(8).Generate();
return 0;
}
J. c++編程問題 回溯演算法 請大師幫忙講解 源代碼不要 上課沒聽懂啊！！
//這題不可用回溯法來解的,因為枚舉的空間太大了,有2^30次方呢,這樣會掛掉的,應該用DP
//dp[i][j][k]表示的是長度為i的串,以j,k為末尾兩位的合法串有多少種. 長度i+1可以從i的加上0或者加上1得到
//dp[i+1][k][p]=sum{dp[i][j][k]}(j!=p&&k!=p)
#include<malloc.h>
#include<stdio.h>
int dp[33][2][2]={0};
int main()
{
int i,j,k,p,n;
dp[1][0][0]=1;
dp[1][0][1]=1;
dp[2][0][0]=1;
dp[2][0][1]=1;
dp[2][1][0]=1;
dp[2][1][1]=1;
for(i=3;i<33;i++)
{
for(j=0;j<2;j++)
{
for(k=0;k<2;k++)
{
for(p=0;p<2;p++)
{
if(j==k&&k==p)continue;
dp[i][k][p]+=dp[i-1][j][k];
}
}
}
}
while(scanf("%d",&n)!=EOF)
{
printf("%d\n",dp[n][0][0]+dp[n][0][1]+dp[n][1][0]+dp[n][1][1]);
}
return 0;
}