单机排序问题最优解的结构及其求法

本文研究了单机排序问题|r_i=0|∑|c_i-d_i|最优解的结构．提出了最优解的紧密规则，以及最优解的近似求法．

背包问题的一种算法

一个人带一个背包上山,其可容纳物品重量的限度为a公斤,设有n种物品可供他选择装人背包中,已知第i种物品每年重量为W_i公斤,在上山的过程中第i种物品的作用价值是携带数量(件数)X_i的函数,认为C_i(X_i).问此人应如何选择携带物品(各几件),使所起作用(总价值)最大?这就是著名的背包问题.类似的问题有工厂里的下料问题,运输中的货物装载问题,空间科学实验站的物品装载问题等等.设X_i为第i种物品的装入件数,则问题的数学模型为: