贪心核加速动态规划算法精确求解适用范围

杨利霞

贪心核加速动态规划算法精确求解适用范围

" v+ v4 f: x. }# _/ E
& X+ F6 I# ^3 H6 J/ l3 T7 ~* ]
$ r  J+ V. t5 k) ], g7 ^针对背包容量折扣系数在 0.8~0.9 时，贪心核加速动态规划算法（GCADP）无法求得逆向强相关折扣
｛0-1｝背包问题实例（IDKP）精确解的问题，为求得 D｛0-1｝KP 实例的精确解，在对 IDKP 实例参数进行分析的
) ?5 _/ j/ O  ~" y基础上，给出 GCADP 算法能精确求解 D｛0-1｝KP 实例的限定条件：任意项集的价值系数满足价值最小项大于
, R' s( g; \/ g! Y* g$ b, L$ \. r价值次大项的 0.99 倍。将该条件应用到 4 类 D｛0-1｝KP 实例的参数设置中，生成新的大规模 D｛0-1｝KP 实
9 e) L& M" @3 J9 v6 x例。对 4 类 D｛0-1｝KP 实例运用 GCADP 和动态规划（DP）进行计算，计算结果表明，新的 4 类 D｛0-1｝KP 实例
1 q1 b; K6 b; E4 g9 [均得到精确解，并且 GCADP 随着数据规模的变大，求解时长增长平缓。
2 O/ H- ?. H; e/ {- R6 Y
: T2 u$ T# P# C% F" N/ k