求教背包问题的方法
展开全部
【问题】 背包问题
问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。
设n个物品的重量和价值分别存储于数组w[ ]和v[ ]中,限制重量为tw。考虑一个n元组(x0,x1,…,xn-1),其中xi=0 表示第i个物品没有选取,而xi=1则表示第i个物品被选取。显然这个n元组等价于一个选择方案。用枚举法解决背包问题,需要枚举所有的选取方案,而根据上述方法,我们只要枚举所有的n元组,就可以得到问题的解。
显然,每个分量取值为0或1的n元组的个数共为2n个。而每个n元组其实对应了一个长度为n的二进制数,且这些二进制数的取值范围为0~2n-1。因此,如果把0~2n-1分别转化为相应的二进制数,则可以得到我们所需要的2n个n元组。
【算法】
maxv=0;
for (i=0;i<2n;i++)
{ B[0..n-1]=0;
把i转化为二进制数,存储于数组B中;
temp_w=0;
temp_v=0;
for (j=0;j<n;j++)
{ if (B[j]==1)
{ temp_w=temp_w+w[j];
temp_v=temp_v+v[j];
}
if ((temp_w<=tw)&&(temp_v>;maxv))
{ maxv=temp_v;
保存该B数组;
}
}
}
问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。
设n个物品的重量和价值分别存储于数组w[ ]和v[ ]中,限制重量为tw。考虑一个n元组(x0,x1,…,xn-1),其中xi=0 表示第i个物品没有选取,而xi=1则表示第i个物品被选取。显然这个n元组等价于一个选择方案。用枚举法解决背包问题,需要枚举所有的选取方案,而根据上述方法,我们只要枚举所有的n元组,就可以得到问题的解。
显然,每个分量取值为0或1的n元组的个数共为2n个。而每个n元组其实对应了一个长度为n的二进制数,且这些二进制数的取值范围为0~2n-1。因此,如果把0~2n-1分别转化为相应的二进制数,则可以得到我们所需要的2n个n元组。
【算法】
maxv=0;
for (i=0;i<2n;i++)
{ B[0..n-1]=0;
把i转化为二进制数,存储于数组B中;
temp_w=0;
temp_v=0;
for (j=0;j<n;j++)
{ if (B[j]==1)
{ temp_w=temp_w+w[j];
temp_v=temp_v+v[j];
}
if ((temp_w<=tw)&&(temp_v>;maxv))
{ maxv=temp_v;
保存该B数组;
}
}
}
参考资料: http://www.chinaunix.net/jh/23/437639.html
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询