背包問題遞歸演算法
㈠ java語言，背包問題，從Excel表中讀取數據
基本概念
問題雛形
01背包題目的雛形是：
有N件物品和一個容量為V的背包。第i件物品的體積是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。
從這個題目中可以看出，01背包的特點就是：每種物品僅有一件，可以選擇放或不放。
其狀態轉移方程是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
對於這方方程其實並不難理解，方程之中，現在需要放置的是第i件物品，這件物品的體積是c[i],價值是w[i],因此f[i-1][v]代表的就是不將這件物品放入背包，而f[i-1][v-c[i]]+w[i]則是代表將第i件放入背包之後的總價值，比較兩者的價值，得出最大的價值存入現在的背包之中。
理解了這個方程後，將方程代入實際題目的應用之中，可得
for (i = 1; i <= n; i++)
for (j = v; j >= c[i]; j--)//在這里，背包放入物品後，容量不斷的減少，直到再也放不進了
f[i][j] = max(f[i - 1][j], f[i - 1][j - c[i]] + w[i]);
問題描述
求出獲得最大價值的方案。
注意：在本題中，所有的體積值均為整數。
演算法分析
對於背包問題，通常的處理方法是搜索。
用遞歸來完成搜索，演算法設計如下：
int make(int i, int j)//處理到第i件物品,剩餘的空間為j 初始時i=m , j=背包總容量
{
if (i == 0) return 0;
if (j >= c[i])//(背包剩餘空間可以放下物品 i )
{
int r1 = make(i - 1, j - w[i]);//第i件物品放入所能得到的價值
int r2 = make(i - 1, j);//第i件物品不放所能得到的價值
return min(r1, r2);
}
return make(i - 1, j);//放不下物品 i
}
這個演算法的時間復雜度是O(n^2)，我們可以做一些簡單的優化。
由於本題中的所有物品的體積均為整數，經過幾次的選擇後背包的剩餘空間可能會相等，在搜索中會重復計算這些結點，所以，如果我們把搜索過程中計算過的結點的值記錄下來，以保證不重復計算的話，速度就會提高很多。這是簡單的「以空間換時間」。
我們發現，由於這些計算過程中會出現重疊的結點，符合動態規劃中子問題重疊的性質。
同時，可以看出如果通過第N次選擇得到的是一個最優解的話，那麼第N-1次選擇的結果一定也是一個最優解。這符合動態規劃中最優子問題的性質。
解決方案
考慮用動態規劃的方法來解決，這里的：
階段：在前N件物品中，選取若干件物品放入背包中
狀態：在前N件物品中，選取若干件物品放入所剩空間為W的背包中的所能獲得的最大價值
決策：第N件物品放或者不放
由此可以寫出動態轉移方程：
我們用f[i][j]表示在前 i 件物品中選擇若干件放在已用空間為 j 的背包里所能獲得的最大價值
f[i][j] = max(f[i - 1][j - W[i]] + P[i], f[i - 1][j]);//j >= W[ i ]
這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：「將前i件物品放入容量為v的背包中」這個子問題，若只考慮第i件物品的策略（放或不放），那麼就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那麼問題就轉化為「前i-1件物品放入容量為v的背包中」，價值為f[v]；如果放第i件物品，那麼問題就轉化為「前i-1件物品放入已用的容量為c的背包中」，此時能獲得的最大價值就是f[c]再加上通過放入第i件物品獲得的價值w。
這樣，我們可以自底向上地得出在前M件物品中取出若干件放進背包能獲得的最大價值，也就是f[m,w]
演算法設計如下：
int main()
{
cin >> n >> v;
for (int i = 1; i <= n; i++)
cin >> c[i];//價值
for (int i = 1; i <= n; i++)
cin >> w[i];//體積
for (int i = 1; i <= n; i++)
f[i][0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= v; j++)
if (j >= w[i])//背包容量夠大
f[i][j] = max(f[i - 1][j - w[i]] + c[i], f[i - 1][j]);
else//背包容量不足
f[i][j] = f[i - 1][j];
cout << f[n][v] << endl;
return 0;
}
由於是用了一個二重循環，這個演算法的時間復雜度是O（n*w)。而用搜索的時候，當出現最壞的情況，也就是所有的結點都沒有重疊，那麼它的時間復雜度是O（2^n)。看上去前者要快很多。但是，可以發現在搜索中計算過的結點在動態規劃中也全都要計算，而且這里算得更多（有一些在最後沒有派上用場的結點我們也必須計算），在這一點上好像是矛盾的。
㈡ 背包問題的演算法
1)登上演算法
用登山演算法求解背包問題 function []=DengShan(n,G,P,W) %n是背包的個數，G是背包的總容量，P是價值向量，W是物體的重量向量 %n=3;G=20;P=[25,24,15];W2=[18,15,10];%輸入量 W2=W; [Y,I]=sort(-P./W2);W1=[];X=[];X1=[]; for i=1:length(I) W1(i)=W2(I(i)); end W=W1; for i=1:n X(i)=0; RES=G;%背包的剩餘容量 j=1; while W(j)<=RES X(j)=1; RES=RES-W(j); j=j+1; end X(j)=RES/W(j); end for i=1:length(I) X1(I(i))=X(i); end X=X1; disp('裝包的方法是');disp(X);disp(X.*W2);disp('總的價值是：');disp(P*X');
時間復雜度是非指數的
2)遞歸法
先看完全背包問題
一個旅行者有一個最多能用m公斤的背包，現在有n種物品，每件的重量分別是W1，W2，...,Wn,
每件的價值分別為C1,C2,...,Cn.若的每種物品的件數足夠多.
求旅行者能獲得的最大總價值。
本問題的數學模型如下：
設 f(x)表示重量不超過x公斤的最大價值，
則 f(x）=max{f(x-i)+c[i]} 當x>=w[i] 1<=i<=n
可使用遞歸法解決問題程序如下:
program knapsack04;
const maxm=200;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
function f(x:integer):integer;
var i,t,m:integer;
begin
if x=0 then f:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(x-i)+c[i];
if m>t then t:=m;
end;
f:=t;
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
writeln(f(m));
end.
說明:當m不大時,編程很簡單,但當m較大時,容易超時.
4.2 改進的遞歸法
改進的的遞歸法的思想還是以空間換時間,這只要將遞歸函數計算過程中的各個子函數的值保存起來,開辟一個
一維數組即可
程序如下:
program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
p:array[0..maxm] of integer;
function f(x:integer):integer;
var i,t,m:integer;
begin
if p[x]<>-1 then f:=p[x]
else
begin
if x=0 then p[x]:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(i-w[i])+c[i];
if m>t then t:=m;
end;
p[x]:=t;
end;
f:=p[x];
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
fillchar(p,sizeof(p),-1);
writeln(f(m));
end.
3)貪婪演算法
改進的背包問題：給定一個超遞增序列和一個背包的容量，然後在超遞增序列中選（只能選一次）或不選每一個數值，使得選中的數值的和正好等於背包的容量。
代碼思路：從最大的元素開始遍歷超遞增序列中的每個元素，若背包還有大於或等於當前元素值的空間，則放入，然後繼續判斷下一個元素；若背包剩餘空間小於當前元素值，則判斷下一個元素
簡單模擬如下：
#define K 10
#define N 10
＃i nclude <stdlib.h>
＃i nclude <conio.h>
void create(long array[],int n,int k)
{/*產生超遞增序列*/
int i,j;
array[0]=1;
for(i=1;i<n;i++)
{
long t=0;
for(j=0;j<i;j++)
t=t+array[j];
array[i]=t+random(k)+1;
}
}
void output(long array[],int n)
{/*輸出當前的超遞增序列*/
int i;
for(i=0;i<n;i++)
{
if(i%5==0)
printf("\n");
printf("%14ld",array[i]);
}
}
void beibao(long array[],int cankao[],long value,int count)
{/*背包問題求解*/
int i;
long r=value;
for(i=count-1;i>=0;i--)/*遍歷超遞增序列中的每個元素*/
{
if(r>=array[i])/*如果當前元素還可以放入背包，即背包剩餘空間還大於當前元素*/
{
r=r-array[i];
cankao[i]=1;
}
else/*背包剩餘空間小於當前元素值*/
cankao[i]=0;
}
}
void main()
{
long array[N];
int cankao[N]={0};
int i;
long value,value1=0;
clrscr();
create(array,N,K);
output(array,N);
printf("\nInput the value of beibao:\n");
scanf("%ld",&value);
beibao(array,cankao,value,N);
for(i=0;i<N;i++)/*所有已經選中的元素之和*/
if(cankao[i]==1)
value1+=array[i];
if(value==value1)
{
printf("\nWe have got a solution,that is:\n");
for(i=0;i<N;i++)
if(cankao[i]==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array[i]);
}
}
else
printf("\nSorry.We have not got a solution.\n");
}
貪婪演算法的另一種寫法，beibao函數是以前的代碼，用來比較兩種演算法：
#define K 10
#define N 10
＃i nclude <stdlib.h>
＃i nclude <conio.h>
void create(long array[],int n,int k)
{
int i,j;
array[0]=1;
for(i=1;i<n;i++)
{
long t=0;
for(j=0;j<i;j++)
t=t+array[j];
array[i]=t+random(k)+1;
}
}
void output(long array[],int n)
{
int i;
for(i=0;i<n;i++)
{
if(i%5==0)
printf("\n");
printf("%14ld",array[i]);
}
}
void beibao(long array[],int cankao[],long value,int count)
{
int i;
long r=value;
for(i=count-1;i>=0;i--)
{
if(r>=array[i])
{
r=r-array[i];
cankao[i]=1;
}
else
cankao[i]=0;
}
}
int beibao1(long array[],int cankao[],long value,int n)
{/*貪婪演算法*/
int i;
long value1=0;
for(i=n-1;i>=0;i--)/*先放大的物體，再考慮小的物體*/
if((value1+array[i])<=value)/*如果當前物體可以放入*/
{
cankao[i]=1;/*1表示放入*/
value1+=array[i];/*背包剩餘容量減少*/
}
else
cankao[i]=0;
if(value1==value)
return 1;
return 0;
}
void main()
{
long array[N];
int cankao[N]={0};
int cankao1[N]={0};
int i;
long value,value1=0;
clrscr();
create(array,N,K);
output(array,N);
printf("\nInput the value of beibao:\n");
scanf("%ld",&value);
beibao(array,cankao,value,N);
for(i=0;i<N;i++)
if(cankao[i]==1)
value1+=array[i];
if(value==value1)
{
printf("\nWe have got a solution,that is:\n");
for(i=0;i<N;i++)
if(cankao[i]==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array[i]);
}
}
else
printf("\nSorry.We have not got a solution.\n");
printf("\nSecond method:\n");
if(beibao1(array,cankao1,value,N)==1)
{
for(i=0;i<N;i++)
if(cankao1[i]==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array[i]);
}
}
else
printf("\nSorry.We have not got a solution.\n");
}
4)動態規劃演算法
解決0/1背包問題的方法有多種，最常用的有貪婪法和動態規劃法。其中貪婪法無法得到問題的最優解，而動態規劃法都可以得到最優解，下面是用動態規劃法來解決0/1背包問題。
動態規劃演算法與分治法類似，其基本思想是將待求解問題分解成若干個子問題，然後從這些子問題的解得到原問題的解。與分治法不同的是，適合於用動態規劃法求解的問題，經分解得到的子問題往往不是互相獨立的，若用分治法解這類問題，則分解得到的子問題數目太多，以至於最後解決原問題需要耗費過多的時間。動態規劃法又和貪婪演算法有些一樣，在動態規劃中，可將一個問題的解決方案視為一系列決策的結果。不同的是，在貪婪演算法中，每採用一次貪婪准則便做出一個不可撤回的決策，而在動態規劃中，還要考察每個最優決策序列中是否包含一個最優子序列。
0/1背包問題
在0 / 1背包問題中，需對容量為c 的背包進行裝載。從n 個物品中選取裝入背包的物品，每件物品i 的重量為wi ，價值為pi 。對於可行的背包裝載，背包中物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價值最高，即p1*x1+p2*x1+...+pi*xi(其1<=i<=n，x取0或1，取1表示選取物品i) 取得最大值。
在該問題中需要決定x1 .. xn的值。假設按i = 1，2，...，n 的次序來確定xi 的值。如果置x1 = 0，則問題轉變為相對於其餘物品(即物品2，3，.，n)，背包容量仍為c 的背包問題。若置x1 = 1，問題就變為關於最大背包容量為c-w1 的問題。現設r?{c，c-w1 } 為剩餘的背包容量。
在第一次決策之後，剩下的問題便是考慮背包容量為r 時的決策。不管x1 是0或是1，[x2 ，.，xn ] 必須是第一次決策之後的一個最優方案，如果不是，則會有一個更好的方案[y2，.，yn ]，因而[x1，y2，.，yn ]是一個更好的方案。
假設n=3, w=[100,14,10], p=[20,18,15], c= 116。若設x1 = 1，則在本次決策之後，可用的背包容量為r= 116-100=16 。[x2，x3 ]=[0,1] 符合容量限制的條件，所得值為1 5，但因為[x2，x3 ]= [1，0] 同樣符合容量條件且所得值為1 8，因此[x2，x3 ] = [ 0，1] 並非最優策略。即x= [ 1，0，1] 可改進為x= [ 1，1，0 ]。若設x1 = 0，則對於剩下的兩種物品而言，容量限制條件為116。總之，如果子問題的結果[x2，x3 ]不是剩餘情況下的一個最優解，則[x1，x2，x3 ]也不會是總體的最優解。在此問題中，最優決策序列由最優決策子序列組成。假設f (i,y) 表示剩餘容量為y，剩餘物品為i，i + 1，...，n 時的最優解的值，即：利用最優序列由最優子序列構成的結論，可得到f 的遞歸式為：
當j>=wi時： f(i,j)=max{f(i+1,j),f(i+1,j-wi)+vi} ①式
當0<=j<wi時：f(i,j)=f(i+1,j) ②式
fn( 1 ,c) 是初始時背包問題的最優解。
以本題為例：若0≤y＜1 0，則f ( 3 ,y) = 0；若y≥1 0，f ( 3 ,y) = 1 5。利用②式，可得f (2, y) = 0 ( 0≤y＜10 )；f(2，y)= 1 5(1 0≤y＜1 4)；f(2，y)= 1 8(1 4≤y＜2 4)和f(2，y)= 3 3(y≥2 4)。因此最優解f ( 1 , 11 6 ) = m a x {f(2，11 6)，f(2，11 6 - w1)+ p1} = m a x {f(2，11 6)，f(2，1 6)+ 2 0 } = m a x { 3 3，3 8 } = 3 8。
現在計算xi 值，步驟如下：若f ( 1 ,c) =f ( 2 ,c)，則x1 = 0，否則x1 = 1。接下來需從剩餘容量c-w1中尋求最優解，用f (2, c-w1) 表示最優解。依此類推，可得到所有的xi (i= 1.n) 值。
在該例中，可得出f ( 2 , 116 ) = 3 3≠f ( 1 , 11 6 )，所以x1 = 1。接著利用返回值3 8 -p1=18 計算x2 及x3，此時r = 11 6 -w1 = 1 6，又由f ( 2 , 1 6 ) = 1 8，得f ( 3 , 1 6 ) = 1 4≠f ( 2 , 1 6 )，因此x2 = 1，此時r= 1 6 -w2 = 2，所以f (3,2) =0，即得x3 = 0。
㈢ 01背包問題
能不能用性價比來做呢
動態規劃看不懂啊
----------------------------------------------------------------------
如果不是0-1問題的話，當然可以通過比較性價比來做，這時候可考慮用貪心演算法；但如果是0-1問題的話就不能單純「用性價比來做」了，因為有可能背包空出一大塊。舉個簡單的例子：一個背包的容量是10KG，
物品A重7KG，價值為14元，
物品B重6KG，價值為11元，
物品C中4KG，價值為7元，
從性價比來看，A最高，但是將A放到背包里以後，無法放進其他物品了，此時總價值為14元；顯然，本問題的最佳方案為將B、C放入背包，總價值為18元。
這就是0-1背包問題為什麼能用動態規劃演算法，而不能用貪心演算法的原因。共同學習:-D
㈣ 背包問題C++遞歸算演算法（求出所有解）
#include <fstream>
#include <vector>
#include <algorithm>
#include <time>
#include <queue>
#include <string>
using namespace std;
ofstream cout("out.txt");
struct Item
{
int v, w;
int x;
Item(int val = 0, int weight = 1, int sel = 0): v(val), w(weight), x(sel) {}
};
bool operator<(const Item& a, const Item& b)
{
return double(a.v) / a.w < double(b.v) / b.w;
}
struct Node
{
unsigned level;
int val;
int B;
int cv, cw;
Node *parent, *lson, *rson;
Node(int L, int V, Node* p):
level(L), val(V), parent(p), lson(0), rson(0) {}
};
class KnapsackBase
{
protected:
vector<Item> Items;
int Cap;
int MaxV;
int cw, cv; // for later use.
Node *Root; // as above.
int nNodes; // counting nodes.
string method;
int SumV(Node *p);
int SumW(Node *p);
int SumW();
float Bound(unsigned i);
void StoreX(Node *p);
void Print();
void DeleteTree(Node* r);
public:
KnapsackBase(const vector<Item>& items, int c):
Items(items), Cap(c)
{
sort(Items.begin(), Items.end(), not2(less<Item>()));
Root = new Node(0, -1, 0);
method = "Greedy";
}
virtual void Pack();
~KnapsackBase()
{
cout << "Destructing " << hex << this << dec << "; ";
nNodes = 0;
DeleteTree(Root);
cout << nNodes << " nodes deleted. -- " + method << endl;
}
};
float KnapsackBase::Bound(unsigned i)
{
int cleft = Cap - cw;
float b = cv;
while (i < Items.size() && Items[i].w <= cleft)
{
cleft -= Items[i].w;
b += Items[i].v;
i++;
}
if (i < Items.size())
b += (float(Items[i].v) / Items[i].w) * cleft;
return b;
}
void KnapsackBase::Pack()
{
unsigned i = 0;
int w = 0;
MaxV = 0;
while (i < Items.size())
{
if (Items[i].w + w <= Cap)
{
Items[i].x = 1;
w += Items[i].w;
MaxV += Items[i].v;
}
else
Items[i].x = 0;
i++;
}
Print();
}
void KnapsackBase::DeleteTree(Node* r)
{
if (r != 0)
{
DeleteTree(r->lson);
DeleteTree(r->rson);
delete r;
nNodes++;
}
}
int KnapsackBase::SumV(Node *p)
{
int s = 0;
while (p != Root)
{
s += Items[p->level - 1].v * p->val;
p = p->parent;
}
return s;
}
int KnapsackBase::SumW(Node *p)
{
int s = 0;
while (p != Root)
{
s += Items[p->level - 1].w * p->val;
p = p->parent;
}
return s;
}
void KnapsackBase::StoreX(Node *p)
{
for (unsigned i = Items.size() - 1; p != Root; p = p->parent, i--)
Items[i].x = p->val;
}
int KnapsackBase::SumW()
{
int s = 0;
for (unsigned i = 0; i < Items.size(); i++)
s += Items[i].w * Items[i].x;
return s;
}
void KnapsackBase::Print()
{
cout << "Result of " + method + " at " << hex << this << dec << endl;
for (unsigned i = 0; i < Items.size(); i++)
cout << Items[i].v << "\t" << Items[i].w << "\t" << Items[i].x << endl;
cout << MaxV << "\t" << SumW() << endl;
}
//----------------------------------------------------------------------------
class KnapsackDFS: public KnapsackBase
{
void DFS(Node* r);
public:
KnapsackDFS(const vector<Item>& items, int c): KnapsackBase(items, c)
{
method = "DFS";
}
void Pack()
{
MaxV = 0;
DFS(Root);
Print();
}
};
void KnapsackDFS::DFS(Node* r)
{
if (r->level == Items.size())
{
int V = SumV(r);
int W = SumW(r);
if (W <= Cap && V > MaxV)
{
StoreX(r);
MaxV = V;
}
}
else
{
r->lson = new Node(r->level + 1, 0, r);
DFS(r->lson);
r->rson = new Node(r->level + 1, 1, r);
DFS(r->rson);
}
}
//----------------------------------------------------------------------------
class KnapsackBFS: public KnapsackBase
{
void BFS();
public:
KnapsackBFS(const vector<Item>& items, int c): KnapsackBase(items, c) {method = "BFS";}
void Pack()
{
MaxV = 0;
BFS();
Print();
}
};
void KnapsackBFS::BFS()
{
queue<Node*> Q;
Node* r;
Q.push(Root);
while (!Q.empty())
{
r = Q.front();
Q.pop();
if (r->level == Items.size())
{
int V = SumV(r);
int W = SumW(r);
if (W <= Cap && V > MaxV)
{
StoreX(r);
MaxV = V;
}
}
else
{
r->lson = new Node(r->level + 1, 0, r);
Q.push(r->lson);
r->rson = new Node(r->level + 1, 1, r);
Q.push(r->rson);
}
}
}
//----------------------------------------------------------------------------
class KnapsackBacktrack: public KnapsackBase
{
void Backtrack(Node* r);
public:
KnapsackBacktrack(const vector<Item>& items, int c): KnapsackBase(items, c) {method = "Backtrack";}
void Pack()
{
MaxV = 0;
cw = 0;
cv = 0;
Backtrack(Root);
Print();
}
};
void KnapsackBacktrack::Backtrack(Node* r)
{
if (r->level == Items.size())
{
int V = SumV(r);
if (V > MaxV)
{
StoreX(r);
MaxV = V;
}
}
else
{
if (cw + Items[r->level].w <= Cap)
{
r->rson = new Node(r->level + 1, 1, r);
cv += Items[r->level].v;
cw += Items[r->level].w;
Backtrack(r->rson);
cv -= Items[r->level].v;
cw -= Items[r->level].w;
}
if (Bound(r->level + 1) > MaxV)
{
r->lson = new Node(r->level + 1, 0, r);
Backtrack(r->lson);
}
}
}
//----------------------------------------------------------------------------
class KnapsackFIFOBB: public KnapsackBase
{
void FIFOBB();
public:
KnapsackFIFOBB(const vector<Item>& items, int c): KnapsackBase(items, c) {method = "FIFOBB";}
void Pack()
{
MaxV = 0;
cv = 0;
cw = 0;
FIFOBB();
Print();
}
};
void KnapsackFIFOBB::FIFOBB()
{
queue<Node*> Q;
Node* r;
Root->cv = 0;
Root->cw = 0;
Q.push(Root);
while (!Q.empty())
{
r = Q.front();
Q.pop();
if (r->level == Items.size())
{
int V = SumV(r);
if (V > MaxV)
{
StoreX(r);
MaxV = V;
}
}
else
{
if (r->cw + Items[r->level].w <= Cap)
{
r->rson = new Node(r->level + 1, 1, r);
r->rson->cv = r->cv + Items[r->level].v;
r->rson->cw = r->cw + Items[r->level].w;
Q.push(r->rson);
}
cv = r->cv;
cw = r->cw;
if (Bound(r->level + 1) > MaxV)
{
r->lson = new Node(r->level + 1, 0, r);
r->lson->cv = r->cv;
r->lson->cw = r->cw;
Q.push(r->lson);
}
}
}
}
//----------------------------------------------------------------------------
class KnapsackLCBB: public KnapsackBase
{
void LCBB();
public:
KnapsackLCBB(const vector<Item>& items, int c): KnapsackBase(items, c) {method = "LCBB";}
void Pack()
{
MaxV = 0;
cv = 0;
cw = 0;
LCBB();
Print();
}
};
class Compare
{
public:
Compare(){}
bool operator()(const Node *p, const Node *q)
{
if (p->B == q->B)
return p->level < q->level;
else
return p->B < q->B;
}
};
void KnapsackLCBB::LCBB()
{
priority_queue<Node*, vector<Node*>, Compare> Q;
Node* r;
Root->cv = 0;
Root->cw = 0;
Root->B = Bound(0);
Q.push(Root);
while (!Q.empty())
{
r = Q.top();
Q.pop();
if (r->level == Items.size())
{
int V = SumV(r);
int W = SumW(r);
if (W <= Cap && V > MaxV)
{
StoreX(r);
MaxV = V;
}
}
else
{
if (r->cw + Items[r->level].w <= Cap)
{
r->rson = new Node(r->level + 1, 1, r);
r->rson->cv = r->cv + Items[r->level].v;
r->rson->cw = r->cw + Items[r->level].w;
r->rson->B = r->B;
Q.push(r->rson);
}
cv = r->cv;
cw = r->cw;
int b;
if ((b = Bound(r->level + 1)) > MaxV)
{
r->lson = new Node(r->level + 1, 0, r);
r->lson->cv = r->cv;
r->lson->cw = r->cw;
r->lson->B = b;
Q.push(r->lson);
}
}
}
}
//----------------------------------------------------------------------------
void test()
{
const int N = 10;
vector<Item> A(N);
for (unsigned i = 0; i < N; i++)
{
A[i].v = 10 + rand() % 20;
A[i].w = 5 + rand() % 25;
}
KnapsackBase B(A, 100);
B.Pack();
cout << endl;
KnapsackDFS E(A, 100);
E.Pack();
cout << endl;
KnapsackBFS R(A, 100);
R.Pack();
cout << endl;
KnapsackBacktrack T(A, 100);
T.Pack();
cout << endl;
KnapsackFIFOBB F(A, 100);
F.Pack();
cout << endl;
KnapsackLCBB C(A, 100);
C.Pack();
cout << endl;
}
int main()
{
time_t t;
srand((unsigned) time(&t));
test();
return 0;
}
㈤ 0/1背包問題
#include<stdio.h>
int i,j,n,C,w[100],v[100],x[100],V[100][100];
int KnapSack();
void main()
{
printf("請輸入背包的容量:");
scanf("%d",&C);
printf("請輸入物品的個數:");
scanf("%d",&n);
printf("請輸入物品的重量:");
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
printf("請輸入物品的價值:");
for(j=1;j<=n;j++)
scanf("%d",&v[j]);
printf("最大價值為:%d\n",KnapSack());
}
int KnapSack()
{
for(i=0;i<=n;i++)
V[i][0]=0;
for(j=0;j<=C;j++)
V[0][j]=0;
for(i=1;i<=n;i++)
for(j=1;j<=C;j++)
if(j<w[i])
V[i][j]=V[i-1][j];
else
{
if(V[i-1][j-w[i]]+v[i]>V[i-1][j])
V[i][j]=V[i-1][j-w[i]]+v[i];
else
V[i][j]=V[i-1][j];
}
j=C;
for(i=n;i>0;i--)
{
if(V[i][j]>V[i-1][j])
{
x[i]=1;
j=j-w[i];
}
else
x[i]=0;
}
return V[n][C];
}
㈥ 我想知道運籌學中旅行背包問題。謝謝！
背包問題是一個非常有名的問題。可以這樣敘述如下。假設有 n 件物品，記為 d1,d2,d3,…… dn。對於每一種物品di (1=<i=<n), 它的重量是wi ,而它的價值為 vi。現在要求用這 n 種物品的子集填滿背包，使其總重量不超過給定的重量限制 TOT，並使得背包的價值盡可能高。
1.實數背包
物品可以一部分放在背包中，那麼直接貪心就行了，把物品按性價比(v[i]/w[i])升序放入即為最優解。
復雜度O(n+nlogn)
2.整數背包
物品只能整個放入背包，不允許拆開放，用動態規劃求解。
dp[i,j]表示前i個物品放入容量為j的背包中可以得到的最優解。
狀態轉移方程：dp[i,j]=max{dp[i-1,j],dp[i-1,j-w[i]]+v[i]}
復雜度O(nm)
3.多重背包
與1、2不同，這里有k個背包，每個背包有不同的容量，其它一樣。
沒什麼好辦法，只能搜索。
對於每個物品i，枚舉它能被放在背包j，也可以不放物品i。
復雜度O(kn)
可以針對不同的題目採取不同的剪枝。
背包問題數學模型為(由於輸入問題,下標很難輸入規范,如c1中1是下標,請注意)
maxZ=c1x1+c2x2+...+cnxn
w1x1+w2x2+...+wnxn<=W
xi>=0,且為整數,i=1,2,...,n
式中：
ck為第k種物品的單位價值，wk是第k種物品的單位重量或體積，W是背包的重量或體積限制。
動態規劃的有關要素如下:
階段k：第k次裝載第k種物品（k=1,2,…,n）
狀態變數sk：第k次裝載時背包還可以裝載的重量(或體積)
決策變數xk：第k次裝載第k種物品的件數
決策允許集合：Dk(sk)={dk|0 xksk/wk，xk為整數}
狀態轉移方程：sk+1=sk－wkxk
階段指標：vk=ckxk
一般來說，用來解決背包問題的方法有遞歸法和貪心法等，但用這兩中方法來解決背包問題都有其不可避免的缺點，遞歸法雖能遍歷搜索空間，找到最優解，但由於此問題的解的空間是以2的N級增長的，所以它只適用於解決小規模的背包問題，而貪心法又很難真正找到最優解，此方法找到的最優解往往與真正的最優解相差很遠。而遺傳演算法作為一種隨機的優化與搜索方法，具有良好的並行性，而且遺傳演算法只需利用目標的取值信息,而無需遞度等高價值信息,因此適用於任何規模。遺傳演算法的高度非線形的不連續多峰函數的優化以及無解析表達式的目標函數的優化,具有很強的通用性。
（如果你是需要計算機編程序的話，答案內容就更多些，現在不曉得你應用背包問題做什麼呢）