背包问题递归算法
㈠ 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级增长的，所以它只适用于解决小规模的背包问题，而贪心法又很难真正找到最优解，此方法找到的最优解往往与真正的最优解相差很远。而遗传算法作为一种随机的优化与搜索方法，具有良好的并行性，而且遗传算法只需利用目标的取值信息,而无需递度等高价值信息,因此适用于任何规模。遗传算法的高度非线形的不连续多峰函数的优化以及无解析表达式的目标函数的优化,具有很强的通用性。
（如果你是需要计算机编程序的话，答案内容就更多些，现在不晓得你应用背包问题做什么呢）