void main()
{
init(7.0);
sortpw();
double max = bbKnapsack();
cout<<endl<<endl<<"最大价值为："<<max<<endl;
}
void init(double cc)
{
c = cc;
cw = 0.0; cp = 0.0; bestp = 0.0;
}
void sortpw()
{
double pw[ARRAY_LENGTH];
for (int i = 0; i < ARRAY_LENGTH; i++)
{
pw[i] = p[i] / w[i];
}
for (i = 0; i < ARRAY_LENGTH; i++)
{
double max = 0.0;
for (int j = 0; j < ARRAY_LENGTH; j++)
{
if (max < pw[j])
{
max = pw[j];
sort[i] = j;
}
}
pw[sort[i]] = 0.0;
}
}
double bound(int i)
{
double cleft = c - cw;
double b = cp;
while (i < ARRAY_LENGTH && w[sort[i]] <= cleft)
{
cleft -= w[sort[i]];
b += p[sort[i]];
i++;
}
if (i < ARRAY_LENGTH)
{
b += p[sort[i]] / w[sort[i]] * cleft;
}
return b;
}
double bbKnapsack()
{
int i = 0; //从0层开始
double bestp = 0.0;
double up = bound(0);
while(i != ARRAY_LENGTH)
{
double wt = cw + w[sort[i]];
if (wt <= c) //左儿子节点为可行节点
{
if (bestp < (cp+p[sort[i]]))
{
bestp = cp + p[sort[i]];
}
TreeNode *node = new TreeNode();
initNode(*node, up, (cp+p[sort[i]]), (cw+w[sort[i]]), i+1); queue.addTail(*node);
}
up = bound(i+1);
if (bestp <= up) //右儿子节点
{
TreeNode *node = new TreeNode();
initNode(*node, up, cp, cw, i+1); queue.addTail(*node);
}
TreeNode tnode = queue.removeMax();
cout<<tnode.weight<<"-"<<tnode.profit<<" "; //输出当前节点的价值(价值递增)
cw = tnode.weight; cp = tnode.profit; up = tnode.upperProfit; i = tnode.level;
}
return bestp;
}
责任编辑：小草
