背包问题

背包问题的描述如下:
  已知有n种物品和一个可容纳m重量的背包,每种物品i的重量为wi。假定将物品i的一部分xi放人背包就会得到pixi的效益,0≤xi≤1,pi>0。采用怎样的装包方法才会使装入背包物品的总效益最大呢?显然,由于背包容量是m,因此,要求所有选中要装入背包的物品总重量不超过m。如果这n件物品的总重量不超过m,则把所有物品装入背包自然获得最大效益。如果这些物品重量的和大于m,则在这种情况下该如何装包呢?这是本节所要解决的问题。根据以上讨论,可将问题形式描述如下:
极 大 化: Σpixi (4.1)
1≤i≤n
约束条件:Σ wixi ≤m (4.2)
1≤i≤n
0≤xi≤1,pi>0,wi>0,1≤i≤n (4.3)
其中,(4.1)式是目标函数,(4.2)和(4.3)是约束条件。满足约束条件的任一集合(x1, …, xn)是一个可行解(即能装下);使目标函数取最大值的可行解是最优解。

 

背包问题的贪心算法:

void Greedy_Knapsack(float p[],float w[],float m[],float x[],int n) {
//p(1:n)和w(1:n)分别含有按p(i)/w(i)≥p(i+1)/w(i+l)排序的 n件物品的
//效益值和重量。m是背包的容量大小,而x(1:n)是解向量
int i;float cu; //cu是背包的剩余容量
for(i=1;i=n;++i) x[i] = 0//将解向量初始化为零
cu = m; //将背包剩余容量cu设成m
for(i=1;i=n;++i) {
if(w[i]>cu) breakelse {x[i] = 1;cu = cu - w[i];}
};//for
if(i≤n) { x(i) = cu/w(i);
return x[];
}// Greedy_Knapsack

 

 

背包问题

 

 有关背包问题还有好几种解法,这里的代码也没有加上去,值得继续深究。

上一篇:第十六章 贪心算法——0/1背包问题


下一篇:执行 Selenium WebDriver脚本抛出 StaleElementReferenceException错误的原因