背包問題演算法

⑴ 背包問題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;
}

⑵ 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數組還是會多選了，你看看。

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

你學過數據結構了嗎？如果學過，那就比較好理解，該演算法的思路和求二叉樹的高度的演算法的思路是十分類似的。把取這i個物體看成i個階段，則該二叉樹有i+1層。其中空背包時為根結點，左孩子則為放棄了第1個物品後的背包，右孩子為選取了第1個物品後的背包。今後在對第i個物品進行選擇時，向左表示放棄，向右表示選取。則遞歸演算法可如下：
int fun(int s, int i, int n) //s傳入的是背包容量, i是進行第i個物品的選取，n為剩餘物品的件數
{
if(s == 0) return 有解；
else if(剩餘的每件物品都裝不進|| n == 0) return 無解；
L = fun(s, i + 1, n - 1); //放棄第i個物品，則下一步的背包容量仍為s，然後看其是否有解，(遞歸調用進入左子樹)
R = fun(s - wi, i + 1, n - 1); //選取第i個物品，則下一步的背包容量為s-wi，然後看其是否有解，(遞歸調用進入右子樹)
return (l, r); //綜合考慮左右兩邊，看哪邊是正解或都無解。其實應該返回 return (L||R);
}

⑷ 用貪心演算法求解背包問題的最優解。

你這個是部分背包么？也就是說物品可以隨意分割？
那麼可以先算出單位重量物品的價值，然後只要從高價值到低價值放入就行了，按p[i]/w[i]降序排序，然後一件一件加，加滿為止！
貪心的思路是：加最少的重量得到更大的價值！
算出單位價值為{6,4,3,2,7,5,2}
加的順序即為5,1,6,2,3,4/7
如果重量不超過就全部都加，超過就加滿為止
不懂可問望採納！
推薦看dd_engi的背包九講，神級背包教程！在此膜拜dd_engi神牛~

⑸ 急，分全拿出來了，演算法中的背包問題的貪心演算法

#include <stdio.h>
#include <iostream.h>

#define MAXWEIGHT 20
#define n 3

float pw[n]={0},x[n]={0};
int w[n]={0},p[n]={0};

void sort(int p[],int w[])
{
int temp1,temp2;
float temp;
int i,j;
for(i=0;i<n;i++)
{
pw[i]=float(p[i])/w[i];
}

for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(pw[i]<pw[j])
{
temp=pw[i],pw[i]=pw[j],pw[j]=temp;
temp1=p[i],temp2=w[i];
p[i]=p[j],w[i]=w[j];
p[j]=temp1,w[j]=temp2;
}
}

}

}

void GreedyKnapsack(int p[],int w[])
{
int m=MAXWEIGHT,i;
for(i=0;i<n;i++) x[i]=0.0;
for(i=0;i<n;i++)
{
if(w[i]>m) break;
x[i]=1.0;
m=m-w[i];
}
if(i<n) x[i]=float(m)/w[i];

}

void main()
{
int i;
printf("請輸入每個物體的效益和重量:\n");
for(i=0;i<n;i++)
{
cin>>p[i]>>w[i];
}
for(i=0;i<n;i++)
{
printf("原物體%d的效益和重量分別為%d,%d:\n",i+1,p[i],w[i]);
}
sort(p,w);
printf("\n\n\n按效益值非遞增順序排列物體:\n");
for(i=0;i<n;i++)
{
printf("物體%d的效益和重量分別為%d,%d 效益值為:%f\n",(i+1),p[i],w[i],pw[i]);

}
GreedyKnapsack(p,w);
printf("\n\n\n最優解為:\n");
for(i=0;i<n;i++)
{
printf("第%d個物體要放%f:\n",i+1,x[i]);
}

}

這是正確的演算法

⑹ 背包問題的貪心演算法C＋＋

為啥不用動態規劃呢？
背包的貪心法是每次都選擇收益最大，如果包還能容納，就放入包裡面，並把這個物品去掉。

⑺ 背包問題的問法變化

以上涉及的各種背包問題都是要求在背包容量（費用）的限制下求可以取到的最大價值，但背包問題還有很多種靈活的問法，在這里值得提一下。但是我認為，只要深入理解了求背包問題最大價值的方法，即使問法變化了，也是不難想出演算法的。
例如，求解最多可以放多少件物品或者最多可以裝滿多少背包的空間。這都可以根據具體問題利用前面的方程求出所有狀態的值（f數組）之後得到。
還有，如果要求的是「總價值最小」「總件數最小」，只需簡單的將上面的狀態轉移方程中的max改成min即可。
下面說一些變化更大的問法。 一般而言，背包問題是要求一個最優值，如果要求輸出這個最優值的方案，可以參照一般動態規劃問題輸出方案的方法：記錄下每個狀態的最優值是由狀態轉移方程的哪一項推出來的，換句話說，記錄下它是由哪一個策略推出來的。便可根據這條策略找到上一個狀態，從上一個狀態接著向前推即可。
還是以01背包為例，方程為f[v]=max{f[v],f[v-c]+w}。再用一個數組g [v]，設g[v]=0表示推出f[v]的值時是採用了方程的前一項（也即f[v]=f[v]），g[v]表示採用了方程的後一項。注意這兩項分別表示了兩種策略：未選第i個物品及選了第i個物品。那麼輸出方案的偽代碼可以這樣寫（設最終狀態為f[N][V]）：
i=N
v=V
while(i>0)
if(g[v]==0)
print 未選第i項物品
else if(g[v]==1）
print 選了第i項物品
v=v-c
另外，採用方程的前一項或後一項也可以在輸出方案的過程中根據f[v]的值實時地求出來，也即不須紀錄g數組，將上述代碼中的g [v]==0改成f[v]==f[v]，g[v]==1改成f[v]==f[v-c]+w也可。
輸出字典序最小的最優方案
這里「字典序最小」的意思是1..N號物品的選擇方案排列出來以後字典序最小。以輸出01背包最小字典序的方案為例。
一般而言，求一個字典序最小的最優方案，只需要在轉移時注意策略。首先，子問題的定義要略改一些。我們注意到，如果存在一個選了物品1的最優方案，那麼答案一定包含物品1，原問題轉化為一個背包容量為v-c[1]，物品為2..N的子問題。反之，如果答案不包含物品1，則轉化成背包容量仍為V，物品為2..N的子問題。不管答案怎樣，子問題的物品都是以i..N而非前所述的1..i的形式來定義的，所以狀態的定義和轉移方程都需要改一下。但也許更簡易的方法是先把物品逆序排列一下，以下按物品已被逆序排列來敘述。
在這種情況下，可以按照前面經典的狀態轉移方程來求值，只是輸出方案的時候要注意：從N到1輸入時，如果f[v]==f及f[v]==f[f-c]+w同時成立，應該按照後者（即選擇了物品i）來輸出方案。 對於一個給定了背包容量、物品費用、物品間相互關系（分組、依賴等）的背包問題，除了再給定每個物品的價值後求可得到的最大價值外，還可以得到裝滿背包或將背包裝至某一指定容量的方案總數。
對於這類改變問法的問題，一般只需將狀態轉移方程中的max改成sum即可。例如若每件物品均是01背包中的物品，轉移方程即為f[v]=sum{f[v],f[v-c]+w}，初始條件f[0][0]=1。
事實上，這樣做可行的原因在於狀態轉移方程已經考察了所有可能的背包組成方案。 這里的最優方案是指物品總價值最大的方案。還是以01背包為例。
結合求最大總價值和方案總數兩個問題的思路，最優方案的總數可以這樣求：f[v]意義同前述，g[v]表示這個子問題的最優方案的總數，則在求f[v]的同時求g[v]的偽代碼如下：
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-c]+w}
g[v]=0
if(f[v]==f[v])
inc(g[v],g[v]
if(f[v]==f[v-c]+w)
inc(g[v],g[v-c])
如果你是第一次看到這樣的問題，請仔細體會上面的偽代碼。 顯然，這里不可能窮盡背包類動態規劃問題所有的問法。甚至還存在一類將背包類動態規劃問題與其它領域（例如數論、圖論）結合起來的問題，在這篇論背包問題的專文中也不會論及。但只要深刻領會前述所有類別的背包問題的思路和狀態轉移方程，遇到其它的變形問法，只要題目難度還屬於NOIP，應該也不難想出演算法。
觸類旁通、舉一反三，應該也是一個OIer應有的品質吧。

⑻ 求背包問題貪心演算法實例結果

找零錢問題：以人民幣1元，2元，5元，10元，20元，50元，100元為例，要求所找的張數最少
背包問題：假設物體重量W1，W2．．．Wn其對應的價值為P1，P2．．．Pn，物體可分割，求裝入重量限制為m的背包中的物體價值最大．可用P/W來解答．
#include<iostream>
#include<algorithm>
using namespace std;
struct good//表示物品的結構體
{
double p;//價值
double w;//重量
double r;//價值與重量的比
}a[2000];
double s,value,m;
int i,n;
bool bigger(good a,good b)
{
return a.r>b.r;
}
int main()
{
scanf("%d",&n);//物品個數
for (i=0;i<n;i++)
{
scanf("%lf%lf",&a[i].w,&a[i].p);
a[i].r=a[i].p/a[i].w;
}
sort(a,a+n,bigger);//調用sort排序函數，你大概不介意吧，按照價值與重量比排序貪心
scanf("%lf",&m);//讀入包的容量m
s=0;//包內現存貨品的重量
value=0;//包內現存貨品總價值
for (i=0;i<n&&s+a[i].w<=m;i++)
{
value+=a[i].p;
s+=a[i].w;
}
printf("The total value in the bag is %.2lf.\n",value);//輸出結果
return 0;
}

⑼ 0-1背包問題用什麼實現演算法最好

我們書上給的0-1背包問題是是用動態規劃方法做的這個演算法是動態規劃的典型應用所以你把動態規劃的思想搞清楚就應該可以理解了下面我把動態規劃的思想給你說一下,希望對你有所幫助.哦..不好意思..時間不多了..你自己到網上找一下這方面的思想..然後結合一個實例認真研讀一下..弄懂之後..你對動態規劃..0-1背包問題就會有比較深入的理解.建議好好學一下演算法..這對計算機專業學生來說很重要..我越來越覺得祝學有所成

⑽ 求完全背包問題的代碼(C語言或C++版)或演算法

背包問題小結- []2006-07-28

做到背包問題覺得很有意思，寫寫看看。
完全背包問題可以用貪心演算法。
代碼如下：

program bag1;
const maxn=10;
var
goods:array[1..maxn,1..3] of integer;
s:array[1..maxn] of real;
i,j:integer;
m,n:integer;
y:integer;
x:real;
function max:integer;
var m:real;
i,j:integer;
begin
m:=0;
for i:=1 to n do
if (goods[i,3]=0) and (m max:=j;
end;

procere choose;
var i,j:integer;

begin
while y begin
if y begin
i:=max;
if m>=y+goods[i,1] then begin goods[i,3]:=1;x:=x+goods[i,2];y:=y+goods[i,1];end else
begin
x:=x+(m-y)*s[i];
y:=m;
end;
end;
end;
end;

begin
fillchar(goods,sizeof(goods),0);
assign(input,'b.txt');
reset(input);
readln(m,n);
for j:=1 to n do
read(goods[j,1]);
readln;
for j:=1 to n do
read(goods[j,2]);
for j:=1 to n do
s[j]:=goods[j,2]/goods[j,1];

close(input);
choose;
writeln(x:5:2);
end.
編得不是很好 ^-^ 獻丑了。

我來說說0/1背包問題。
狀態：當前物品n
算符：j=0（當前物品不放入背包） 或 j=1（當前物品放入背包）
這就很好說了，還是把yes函數一改，問題OK了。
代碼如下：

program bag2;
const maxn=10;
var i:integer;
goods:array[1..maxn,1..3] of integer;{原始數據}
s:array[1..maxn] of integer;{當前的狀態}
r:array[1..maxn] of integer;{當前的總質量}
m:integer;{背包容量}
max:integer;{物品個數}
procere try(n:integer);
var j:integer;

{function yes:boolean;
var k:integer;
t:integer;
mn:integer;
begin
mn:=0;
t:=goods[n,3];
goods[n,3]:=j;
for k:=1 to n do
if goods[k,3]=1 then inc(mn,goods[k,1]);
goods[n,3]:=t;
if mn>m then yes:=false else yes:=true;
end;}

begin
if n=max+1 then begin if x for i:=1 to max do s[i]:=goods[i,3]; {保存最優解}end
end else
begin
if r[n-1]>m then exit;{已超過背包總容量}
for j:=1 downto 0 do
begin
if j=1 then r[n]:=r[n-1]+goods[n,1];
if j=0 then r[n]:=r[n]-goods[n,1];
if {yes}r[n]<=m then begin goods[n,3]:=j;try(n+1);goods[n,3]:=0;end
end;
end;
end;

begin
assign(input,'b.txt');
reset(input);
readln(m,max);
for i:=1 to max do
read(goods[i,1]);
readln;
for i:=1 to max do
read(goods[i,2]);
close(input);
try(1);
for i:=1 to 7 do
write(s[i]:3);
writeln;
writeln(x);
end.

用yes 函數要從頭到當前求已裝入背包物品的總質量，時間效率不高。所以我們引入r[n]數組來記錄當前背包總質量（很好用！）注意用r[n-1]>m來做剪枝，以再次提高時間效率。

DC跟我說可以用二進制解此類問題。我覺得很有創意，也說說。比如8個物品，每個物品有0/1兩種狀態所以我們從(00000000)(二進制 )到（11111111）（二進制）循環即可。然後在分離十進制數對應起來即可。但在實際的操作中發現效率比回溯還低，我想有兩方面的原因：1、顯而易見，不可能做剪枝。2、每一次結果都要從1到8求和十效率降低。不過這確實是一種很新穎的演算法。