(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211140581.X (22)申请日 2022.09.20 (71)申请人 浙江保融科技股份有限公司 地址 311121 浙江省杭州市余杭区仓前街 道文一西路15 00号3幢23 6室 (72)发明人 葛佳飞　包恩伟　董兴荣　张一鸣　 (74)专利代理 机构 杭州华鼎知识产权代理事务 所(普通合伙) 33217 专利代理师 魏亮 (51)Int.Cl. G06F 17/11(2006.01) G06F 17/16(2006.01) G06Q 10/04(2012.01) G06F 9/50(2006.01) (54)发明名称 一种有限资源下的有序背包问题分段动态 规划求解方法 (57)摘要 本发明公开了一种有限资源下的有序背包 问题分段动态规划求解方法， 包括： 对于输入的 数据， 预设物品数量 n， 每个物品的序号 i、 重量 和价格 ， 背包承重W； 设定状态数组F的最大 存储； 读取可用内存大小， 通过状态数组的最大 存储和可用内存大小之间的最小值确定状态数 组F的元素数量S； 对物品按重量从轻到重进行排 序， 排序后物品的序号记为j， 记录序号j与序号i 的对应关系； 定义状态数组的行数为n， 列数 ； 定义第t阶段背包承重， 依次判断每个物品是否 被选择放入背包， 计算第t阶段背包中物品的总 价格； 如果满足第一预设条件， 则重新定义第t+1 阶段背包承重， 计算第t+1阶段背包中物品的总 价格， 直至满足第二预设条件， 输出 结果。 权利要求书2页 说明书8页 附图4页 CN 115221460 A 2022.10.21 CN 115221460 A 1.一种有限资源下的有序背包问题分段动态规划求 解方法， 其特 征在于， 包括： A1： 对于输入的数据， 预设物品数量n， 每个物品的序号i、 重量 和价格 ， 背包承重 W， 其中 ； A2： 设定状态数组F的最大存 储； A3： 读取可用内存大小， 通过状态数组的最大存储和可用内存大小之间的最小值确定 状态数组F的元 素数量S； A4： 对物品按重量从轻到重进行排序， 排序后物品的序号记为j， 记录序号j与序号i的 对应关系； A5： 定义状态数组的行 数为n， 列数 ， 状态数组F记为 ； A6： 定义第t阶段背包承重， 依次判断每个物品是否被选择放入背包， 计算第t阶段背包 中物品的总价格； 如果满足第一预设条件， 则重新定义第t+1阶段背包承重， 计算第t+1阶段 背包中物品的总价格， 直至满足第二预设条件， 输出 结果。 2.根据权利要求1所述的一种有限资源下的有序背包问题分段动态规划求解方法， 其 特征在于， 步骤A5的过程包括： 定义状态数 组的行数为n， 列数c为S/n向下取整， 状态数 组的 列序号为1, 2,  …, c， 代表背包承重的档次， 记为 。 3.根据权利要求1所述的一种有限资源下的有序背包问题分段动态规划求解方法， 其 特征在于， 步骤A5中， 状态数组F中的元素记为F[i][j]， 代表状态数组F中第i行第j列的元 素， 令 且不存入状态数组。 4.根据权利要求1所述的一种有限资源下的有序背包问题分段动态规划求解方法， 其 特征在于， 步骤A6中， 起始时t为1， 定义第一阶段背包承重为 ， 单位 向下取 整， 每个物品的重量 向上取整。 5.根据权利要求4所述的一种有限资源下的有序背包问题分段动态规划求解方法， 其 特征在于， 步骤A6中， 所述依次判断每 个物品是否被选择放入背包， 包括： 将第1个物品放入背包， 填入第一行状态数组F[1]， 当 时， ， 否则 ； 对是否将第j个物品放入背包进行选择， 对于状态数组元素 而言， 新的状态为 ， 当 时， 表示物品j被选择放入背包， 反 之被选择不 放入背包， 依次填入第j行状态数组F[j]； 从状态数组的最后一个元素 开始判断物品j是否被选择放入背包， 如果 ， 则物品 对应的物品序号i记入被装入背包的序 号列表X， 剩余状态子数组为 ， 如果 ， 剩余状态子数组为 ； 剩余状态子数组 为原状态数组或剩余状态子数组的第1行至第i行、 第1列至第j列 构成的子矩阵；权　利　要　求　书 1/2 页 2 CN 115221460 A 2对任意剩余状态子数组， 假设其 为 ， 当 时， 当 则物品j对应的物品序号i记入被装入背包的序号列表X， 新的剩余状态子数组 ， 如果 ， 新的剩余状态 子数组 ， 重复本步骤直到新的剩余状态子数组为空。 6.根据权利要求5所述的一种有限资源下的有序背包问题分段动态规划求解方法， 其 特征在于， 步骤A6中， 所述第一预设条件为： ； 前一阶段完成后， 剩余物品中剔除 的物品， 其数量仍记为 ， 序号仍记 为j， ， 记录j与物品原始序号i的对应关系， 新的列 数 ， 如果 ， 定义第t阶段背包承重为 ， 单位 ， 剩 余的每个物品的重量 。 7.根据权利要求6所述的一种有限资源下的有序背包问题分段动态规划求解方法， 其 特征在于， 步骤A6中， 所述第二预设条件为： ； 重复执行不同阶段的计算任 务， 直到 ， 定义该阶段背包承重为 ， 仍记为 ； 计算背包中物品的总价格 ， 输出背包中装 入物品的序号列表X、 总价格P。权　利　要　求　书 2/2 页 3 CN 115221460 A 3