《表1 组内排序后序号存入数组H示例》

  提示：宽带有限、当前游客访问压缩模式

本系列图表出处文件名：随高清版一同展现

《求解折扣{0-1}背包问题的新遗传算法》

1. 获取 高清版本忘记账户？点击这里登录

1. 下载图表忘记账户？点击这里登录

演化算法求解背包问题中，使用价值密度作为衡量物品装入背包的选择尺度是常用的策略。D{0-1}KP与普通的0-1KP不同，物品以项集为单位进行选择，每项集只能有一项被选中。GADKP算法利用了D{0-1}KP这一特征使用逐层贪心策略选择物品。为此，需要完成下面的预备工作。按物品的价值密度进行了逐层排序：对每组物品项3i，3i+1和3i+2，（0≤i≤n-1）按价值密度vj/wj（j∈{3i，3i+1，3i+2}）非升序排序，将排好序的组内序号存入二维数组H[0…n-1，0…2]的第i行对应位置。然后，将各组中第一名按他们的价值密度比以非升序排序，排序后的序号存入二维数组G[0…n-1，0…2]的第一列；将各组第二名按他们的价值密度比非升序排序，排序后的序号存入数组G的第二列；将各组第三名按他们的价值密度比非升序排序，排序后的序号存入数组G的第三列。例如一个包括7组项目组的D{0-1}KP实例，价值集合V={{125，821，946}，{359，987，1346}，{258，763，1021}，{107，622，729}，{474，744，1218}，{150，640，490}，{260，497，757}}，重量集合为W={{25，721，725}，{259，887，934}，{158，663，777}，{7，522，528}，{374，644，664}，{50，390，410}，{160，397，549}}。那么，其对应的二维数组H如表1所示，对应的数组G如表2所示。G[0，0]中数字为3，表示第3组（组序号从0开始）的价值比最高的项在所有组中最高，而第3组价值比最高的项就是H[3，0]的值，本实例中为0，即表示第3组中第0项（组内序号从0编号）。