背包問題分支界限演算法c語言

❶ 用分支限界法求解0/1背包問題

1.問題描述：已知有N個物品和一個可以容納M重量的背包，每種物品I的重量為WEIGHT，一個只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的總效益最大。

2.設計思想與分析：對物品的選取與否構成一棵解樹，左子樹表示不裝入，右表示裝入，通過檢索問題的解樹得出最優解，並用結點上界殺死不符合要求的結點。

#include

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 {
cout<<"請輸入第件"<cin>>bag[i].weight;
cout<<"請輸入第件"<cin>>bag[i].benefit;
bag[i].flag=0;//初始標志為不裝入背包
cout< }

}

int getbound(int num, int *bound_u)//返回本結點的c限界和u限界
{
for(int w=curw, p=curp; 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 {
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; iif(bag[i].flag>0)

cout<
｝

參考：
http://cache..com/c?word=%B7%D6%D6%A7%3B%CF%DE%BD%E7%3B%B7%A8%3B%C7%F3%BD%E2%3B0%2C1%3B%B1%B3%B0%FC%3B%CE%CA%CC%E2&url=http%3A//www%2Edaxiongonline%2Ecom/dvbbs/dispbbs%2Easp%3FboardID%3D31%26ID%3D1016&b=10&a=0&user=

❷ 分別用隊列和優先順序隊列分支限界法解0—1背包問題

利用優先順序分支限界法設計0/1背包問題的演算法，掌握分支限界法的基本思想和演算法設計的基本步驟，注意其中結點優先順序的確定方法，要有利於找到最優解的啟發信息。

要求：設計0/1背包問題的分支限界演算法，利用c語言（c++語言）實現演算法，給出程序的正確運行結果。

注意：
1. 把物品按照單位體積的價值降序排列；
2. 構造優先順序分支限界法的狀態空間樹，共n層，第i層每個節點的兩個分支分別代表第i個物品的取和不取；
3. 節點上需要保存的值有：S代表已裝入背包的物品的總體積，V代表已裝入背包的物品的總價值，u代表當前節點的上界，計算公式如下：
u=V+（C-S）（vi+1/si+1）
其中C是背包的總容積，vi+1代表第i+1個物品的價值，si+1代表第i+1個物品的體積。
4. 選擇適當的數據結構（如最大堆，或者基本的線性數組）實現演算法，輸出最後結果。

❸ 分支限界法兩道題目

利用優先順序分支限界法設計0/1背包問題的演算法，掌握分支限界法的基本思想和演算法設計的基本步驟，注意其中結點優先順序的確定方法，要有利於找到最優解的啟發信息。要求：設計0/1背包問題的分支限界演算法，利用c語言（c++語言）實現演算法，給出程序的正確運行結果。注意：1.把物品按照單位體積的價值降序排列；2.構造優先順序分支限界法的狀態空間樹，共n層，第i層每個節點的兩個分支分別代表第i個物品的取和不取；3.節點上需要保存的值有：S代表已裝入背包的物品的總體積，V代表已裝入背包的物品的總價值，u代表當前節點的上界，計算公式如下：u=V+（C-S）（vi+1/si+1）其中C是背包的總容積，vi+1代表第i+1個物品的價值，si+1代表第i+1個物品的體積。4.選擇適當的數據結構（如最大堆，或者基本的線性數組）實現演算法，輸出最後結果。

❹ c語言背包問題，求高手解答

對01背包求解，方法有回溯法、分支限界法、動態規劃法等。給你一個較容易理解的解法：窮舉搜索。問題求解的結果實際上是一個01序列，0表示該物品未裝入背包，1表示裝入背包。以本題為例，設求解結果為0111011，表示第0個和第4個未裝入，其他均裝入。關鍵就是如何找到這個01序列。設物品數量為n，則解空間為2^n，所以窮舉搜索的時間效率為O(2^n)。
#include <stdio.h>
#define N 7
int weight[N]={35, 30, 6, 50, 40 10, 25}, cost[N]={10, 40, 30, 50, 35, 40, 30};
char name[] = "ABCDEFG";
int max = 0, Max[N]; /*max用於存放最大價值，Max用於存放最優解向量*/
int v[N]; /*v：求解時用於存放求解過程向量*/
template <class T>
void Swap(T &a, T &b)
{
T tmp = a;
a = b, b = tmp;
}
void Knapsack(int step, int bag, int value1, int value2, int n)
/*step表示第step步的選擇（即第step個物品的選擇），bag為背包剩餘容量，value1表示包中現有物品總價值，value2表示剩餘物品總價值，n為物品總數量*/
{
int i;
if((step >= n) || (weight[step] > bag) || (value1 + value2 <= max)) /*如果所有物品都選擇完畢或剩餘的物品都放不進或者包中物品總價值與剩餘物品總價值之和小於等於目前的已知解，則找到一個解(但不一定是最終解或更優解)*/
{
for(i = step; i < n; i++) v[i] = 0; /*剩餘的物品都不放入*/
if(value1 > max) /*如果本次求得的解比以往的解更優，則將本次解作為更優解*/
{
max = value1;
for(i = 0; i < n; i++) Max[i] = v[i]; /*將更優解保存到Max向量中*/
}
return;
}
v[step] = 0, Knapsack(step + 1, bag, value1, value2 - cost[step], n); /*不將第step個物品放入背包，第step個物品的價值被放棄，進行下一步的選擇*/
v[step] = 1, Knapsack(step + 1, bag - weight[step], value1 + cost[step], value2 - cost[step], n); /*將第step個物品放入背包，進行下一步的選擇*/
}
void main( )
{
/*輸入數據：背包容量、物品數量、重量、價值 代碼略*/
int bag = 150, i, j, min, totalcost;
/*按物品重量從小到大的順序對物品排序，排序時cost向量中的相對順序也要作相應移動*/
for(i = 0; i < N - 1; i++) {
for(min = i, j = i + 1; j < N; j++)
if(weight[j] < weight[min]) min = j;
if(i != min) {
Swap(weight[i], weight[min]);
Swap(cost[i], cost[min]);
Swap(name[i], name[min]);
}
}
for(totalcost = 0, i = 0; i < N; i++) totalcost += cost[i]; /*求總價值*/
Knapsack(0, bag, 0, totalcost, N); /*bag為空背包容量, totalcost為物品總價值, N為物品數量*/
/*以下輸出解*/
printf("最大價值為: %d。\n裝入背包的物品依次為：\n", max);
for(i = 0; i < N; i++)
if(Max[i]) printf("%c\t", name[i]);
printf("\n");
}

我的回答你滿意嗎？如果滿意，就請採納哦，或者你也可以繼續追問。

❺ C語言演算法求助：背包問題

//如果每種商品只有一件，是0-1背包問題
讀入的數據N代表物品個數
V代表背包容量。
//對於你的例子
，輸入為
//5
16
//2
3
//3
2
//4
3
//5
7
//6
9
//輸出為21
#include
<iostream>
using
namespace
std;
#define
MAXSIZE
1000
int
f[MAXSIZE
+
1],
c[MAXSIZE
+
1],
w[MAXSIZE
+
1];
int
main()
{
int
N,
V;
cin
>>
N
>>
V;
int
i
=
1;
for
(;
i
<=
N;
++i)
{
cin
>>
c[i]
>>
w[i];
}
for
(i
=
1;
i
<=
N;
++i)
{
for
(int
v
=
V;
v
>=
c[i];
--v)
//c[i]可優化為bound,
bound
=
max
{V
-
sum
c[i,...n],
c[i]}
{
f[v]
=
(f[v]
>
f[v
-
c[i]]
+
w[i]
?
f[v]
:
f[v
-
c[i]]
+
w[i]);
}
}
//當i=N時，可以跳出循環單獨計算F[V]
cout
<<
f[V]
<<
'\n';
system("pause");
return
0;
}
//如果每種可以有多個，是完全背包問題，

❻ 【在線等】分支限界法01背包問題C語言

哈哈,選我吧!#include
#include
usingnamespacestd;
#defineN100
class
HeapNode
{
public:
doubleupper,price,weight;
intlevel,x[N];
};
doubleMaxBound(inti);
doubleKnap();
voidAddLiveNode(doubleup,doublecp,doublecw,boolch,intlevel);
stackHigh;
doublew[N],p[N];
doublecw,cp,c=7;
intn=4;
intmain()
{
inti;
for(i=1;i>w[i];
for(i=1;i>p[i];
coutbestp)bestp=cp+p[i];
AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);
}
up=MaxBound(i+1);
if(up>=bestp)
AddLiveNode(up,cp,cw,false,i+1);
if(High.empty())returnbestp;
HeapNodenode=High.top();
High.pop();cw=node.weight;cp=node.price;up=node.upper;
i=node.level;
}
}

❼ C語言 背包問題 遞歸演算法

if(n==0)應該改成

if(n<0)才對，表示沒有物品可選了。我的一個改進，但輸出選擇項還是有問題！

#include<stdio.h>
#include<conio.h>
#defineN3
intMaxW(intn,intC,int*Volume,int*Weight,int*Select){
intW=0,W1=0;
if(n<0){//沒有物品了
return0;
}
W=MaxW(n-1,C,Volume,Weight,Select);//沒放入n之前的重量
if(C>=Volume[n]){//背包剩餘空間可以放下物品n
W1=MaxW(n-1,C-Volume[n],Volume,Weight,Select)+Weight[n];//放入n所能得到的重量
Select[n]=0;
if(W1>W){//放入n能獲得更大的重量
Select[n]=1;
W=W1;
}
}
returnW;
}

intmain(){
intC=8,W,i;
//intVolume[N]={1,2,3,4,5};//物品體積
//intWeight[N]={1,2,5,7,8};//物品重量
intVolume[N]={2,3,5};//物品體積
intWeight[N]={5,8,7};//物品重量
intSelect[N]={0};//選擇標記
W=MaxW(N-1,C,Volume,Weight,Select);
printf("MaxWeight=%d,SelectList[index(volume,weight)]:
",W);
for(i=0;i<N;++i){
if(Select[i]){
printf("%d(%d,%d)",i,Volume[i],Weight[i]);
}
}
printf("
Finished!
");
getch();
return0;
}

其中的Select數組還是會多選了，你看看。

❽ 用分支限界法，寫01背包問題！C語言版！急~~~~~~能不用結構體，盡量別用！

class Object{
friend int Knapsack(int *,int *,int,int,int *);
public :
int operator<=(Object a)const {return(d>=a.d);}
private:
int ID;
floa d;//單位重量價值
};

template <class Typew,class Typep> class Knap;
class bbnode{
friend Knap<int,int>;
friend int Knapsack （int *,int *,int,int,int *）;
private:
bbnode * parent;
bool LChild;
};
template<class Typew,class Typep>
class Heap Node{
friend Knap<Typep>;
public:
operator Typep ()const{return uprofit;}
private:
Typep uprofit,profit;//結點價值上界
Typew weight;//結點所相應的價值
int level;//結點所相應的重量
bbnode *ptr;//指向活結點在子集樹中相應結點的指針
}；
template<class Typew,class Typep>
class Knap{
friend Typep Knapsack(Typep *,Typew *,Typew,int,int *);
public:
Typep MaxKnapsack();
private:
MaxHeap<HeapNode<Typep,Typew>>* H;
Typep Bound(int i);
void AddLiveNode(Typep up,Typep cp,Typew cw ,bool ch,int level);
bbnode * E;//指向擴展結點的指針
Typew c;//背包容量
int n;//物品總數
Typew * w;//物品重量數組
Typep * p;//物品價值數組
Typew cw;//當前裝包重量
Typep cp;//當前裝包價值
int * bestx;//最優解
}；
上界函數：
template<class Typew,class Typep>
Typep Knap<Typew,Typep>::Bound(int i)
{//計算結點所相應價值的上界
Typew clef=c-cw;//剩餘容量
Typep b=cp;//價值上界
//以物品單位重量價值遞減次序裝剩餘容量
while(i<n&&w[i]<=cleft){
cleft-=w[i];
b+=p[i];
i++;
}
//裝填剩餘容量裝滿背包
if（i<=n）b+=p[i]/w[i] * clef;
return b;
}
函數AddLiveNode將一個新的活結點插入到子集樹和優先隊列中
template<class Typep,class Typew>
void Knap<Typep,Typew>::AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int lev)
{//將一個新的活結點插入到子集樹和最大堆H中
bbnode * b=new bbnode;
b->parent=E;
b->LChild=ch;
HeapNode<Typep,Typew>N;
N.uprofit=up;
N.profit=cp;
N.weight=cw;
N.level=lev;
N.ptr=b;
H->Insert(N);
}
template<class Typew,class Typep>
Typep Knap<Typew,Typep>::MaxKnapsack()
{//優先隊列式分支限界法，返回最大價值，bestx返回最優解
//定義最大堆的容量為1000
H=new MaxHeap<HeapNode<Typep,Typew>>(1000);
//為bestx分配存儲空間
bestx=new int[n+1];
//初始化
int i=1;
E=0;
cw=cp=0;
Typep bestp=0;//當前最優值
Typep up=Bound(1);//價值上界
//搜索子集空間樹
while(i!=n+1){
//非葉結點，檢查當前擴展結點的左兒子節點
Typew wt=cw+w[i];
if(wt<=c){//左兒子節點為可行結點
if(cp+p[i]>bestp)bestp=cp+p[i];
AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}
up=Bound(i+1);
//檢查當前擴展結點的右兒子節點
if(up>=bestp)//右子樹可能含最優解
AddLiveNode(up,cp,cw,false,i+1)
//曲下一個結點
HeapNode<Typep,Typew> N;
H->DeleteMax(N);
E=N.ptr;
cw=N.weight;
cp=N.profit;
up=N.uprofit;
i=N.level;
}
for ( int j=n;j>0;j-- )
{
bextx[j]=E->LChile;
E=E->parent;
}
return cp;
}

❾ 背包問題，C語言編程

原始題目： 有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是
w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容
量，且價值總和最大。（取自網路）
問題簡化： 1. 背包可容納總重量為M
2. 有n個物品，每個重量為m[0]. m[1]. m[2] ......m[i] 對應每個物品的
價值為s[0]. S[1]. S[2]....s[i] (i<=n)
3. 放入第i個物品,比較m[i]和M的大小,不超過M則記錄下當前價值s
4. 最終取得最大值s

實現方法：
定義三個浮點型一維數組float m[[n]和s[n]和y[n] 定義float M,float a,b定義int n,j, int i

請輸入背包容量大小M：
please input the number of the things：
please input the value of the things：
把輸入數據按順序分別定義到數組中（若可以的話，把m[n]的數據由小到大排序，判斷最小值m[0]和M的大小，若m[0]>M，輸出error）
創建一個棧（這里的東西不太懂—-—）
將第一個數據壓入棧底,定義i=0，把當前的m[i]賦值給a，s[i]賦值給b,把當前i存放進數組y[n]，以後在每次比較過程中，都把較大b值所對應的物品數存放進y[n]中
判斷a<M（這里，若在4已經做過，則可省略，第一個數據一定小於M）
判斷a+m[++i]<=M，為真，把第i（注意，此時i已經自增了，這個i是數組中的下標）個數據壓入棧，賦值a=a+m[++i]，比較b和b+s[++i]的大小，賦值b=b+s[++i]（理論上，物品價值總該是為正的吧，若是這樣的話，不用比較大小了，直接賦新值，直到跳出第一輪循環為止；另外有一種設想，若價值全為正，可以轉而把問題這樣簡化：即給定容量大小和全為正的價值物品，現在想辦法讓背包放入物品的數量最多 就行了）；若為假，轉10
如此進行一輪循環，直到出現10，此時b為一輪循環的最大值，return b,y[n]
當a+m[++i]>M，從棧中彈出m[i-2]，a=a-m[i-2],,當i原本就小於等於2的時候，則清除棧中數據，轉12，判斷a+m[i]<=M，為真，比較b和b-s[i-2]+s[i]，並把較大值賦給b，繼續向下比較，這時候就不用壓入棧中了,再定義一個j=1
判斷a+m[i+j]<=M,為真，比較b和b-s[i-2]+s[i+j]大小，較大值賦給b，為假，從棧中彈出m[i-3]，當i原本就小於等於3的時候，則清除棧中數據，轉12，判斷a+m[i]<=M，為真，比較b和b-s[i-3]+s[i]（注意，這個b一直在被賦予最新值），如此進行第一輪循環，用for語句實現，因為下面還有嵌入
此時棧中沒有數據，並且，已經把m[0]為棧底的循環計算完畢，現在開始計算m[1]為棧底的循環，在這一循環，忽略掉m[0]，所有可能情況已經在8-11計算過

依此往下，直到棧底被壓入的是m[n]為止，計算完畢，輸出b，並且輸出數組y[n]
碰巧幫同學，也是這個問題，希望能幫助你。

❿ 背包問題(C語言)

我一下別人的遞歸演算法，假如你有時間限時的話，那我就用動態規劃幫你重新code一個

#include <stdio.h>
#define N 100 //物品總種數不是常量，沒法根據它來決定數組的長度，只有先定義個長度了
int n;//物品總種數
double limitW;//限制的總重量
double totV;//全部物品的總價值
double maxv;//解的總價值
int option[N];//解的選擇
int cop[N];//當前解的選擇
struct {//物品結構
double weight;
double value;
}a[N];
//參數為物品i,當前選擇已經達到的重量和tw,本方案可能達到的總價值
void find(int i,double tw,double tv)
{
int k;
//物品i包含在當前方案的可能性
if(tw+a[i].weight <= limitW){
cop[i]=1;
if(i<n-1)find(i+1,tw+a[i].weight,tv);
else{
for(k=0;k<n;++k)
option[k]=cop[k];
maxv=tv;
}
}
cop[i]=0;
//物品i不包含在當前方案的可能性
if(tv-a[i].value>maxv){
if(i<n-1)find(i+1,tw,tv-a[i].value);
else{
for(k=0;k<n;++k)
option[k]=cop[k];
maxv=tv-a[i].value;
}
}
}
void main()
{
int k;
double w,v;
printf("輸入物品種數:");
scanf("%d",&n);
printf("輸入各物品的重量和價值:");
for(totV=0.0,k=0;k<n;++k){
scanf("%lf %lf",&w,&v);
a[k].weight = w;a[k].value = v;
totV += v;
}
printf("輸入限制重量:");
scanf("%lf",&limitW);
maxv=0.0;
for(k=0;k<n;++k)cop[k]=0;
find(0,0.0,totV);
for(k=0;k<n;++k)
if(option[k])printf("%4d",k+1);
printf("總價值為: %2f",maxv);
}