§3背包间题 有 个人背包上山，其可携带物品重量限度为a公厅。设有n种 物品可供他选择装入背包中，己知第种物品每件重为w公斤，在 上山过程中的作用是数量x的函数c(x)。间此人应如何选择携带 物品（各几件），使所起作用最大。这就是著名的背包间题。类似 的同题有运输中的货物装载数量、人造卫星内的物品装载间题等 设x为第种物品的装入数量，则问题的数学模型为： max Z=>c(x 含a ,≥0且尚营款，=1,2，e 这是一个整数规划问题。 如果x只取0或1，又称0-1背包问题 这类问题可以用动态规划方法求解。 按可装入背包的物品的类别分阶段：k=1,2,.,n 犬态变量x表示允许装入的第k种物品至第n种物品的总重量： 快策变量u表示装入的第k种物品的件数，则状态转移方程为： k+1-Xk Uk Wk 设人(x,)为装入第k种物品到第种物品所对应的最大使用价 值。则动态规划基本方程是：§3 背包问题 有一个人背包上山，其可携带物品重量限度为a公斤。设有n种 物品可供他选择装入背包中，已知第i种物品每件重为wi公斤，在 上山过程中的作用是数量xi的函数ci (xi )。问此人应如何选择携带 物品（各几件），使所起作用最大。这就是著名的背包问题。类似 的问题有运输中的货物装载数量、人造卫星内的物品装载问题等。 设xi为第i种物品的装入数量，则问题的数学模型为： = ( ) = n i Z ci xi 1 max wx a n i i  i  =1 Xi≥0且为整数，i=1,2, …,n 这是一个整数规划问题。如果xi只取0或1，又称0-1背包问题。 这类问题可以用动态规划方法求解。 按可装入背包的物品的类别分阶段：k=1，2，…，n. 状态变量xk表示允许装入的第k种物品至第n 种物品的总重量； 决策变量uk表示装入的第k种物品的件数，则状态转移方程为： xk+1=xk-uk wk. 设fk（xk）为装入第k种物品到第n种物品所对应的最大使用价 值。则动态规划基本方程是：