请下载论文,论文为word格式,只上传部分查看,如果需要此参考论文,请点击-下载论文,下载资料。
一、问题描述
01背包问题:
一个商人带着一个能装m千克的背包去收购货物。现
有n种货物,且第i种货物有wi千克,可获得pi元。假设货物不能拆零,请编写算法帮助商人收购货物,获得最高利润。
二、算法设计与分析
枚举法分析:
设n个物品的重量和价值分别存储于数组w[ ]和v[ ]中,限制重量为tw.考虑一个n元组(x0,x1,…,xn-1),其中xi=0 表示第i个物品没有选取,而xi=1则表示第i个物品被选取。用枚举法解决背包问题,需要枚举所有的选取方案,而根据上述方法,我们只要枚举所有的n元组,就可以得到问题的解。
显然,每个分量取值为0或1的n元组的个数共为2n个。而每个n元组其实对应了一个长度为n的二进制数,且这些二进制数的取值范围为0~2n-1.因此,如果把0~2n-1分别转化为相应的二进制数,则可以得到我们所需要的2n个n元组。