【问题描述】有 n 件物品和一个容量为 C、容积为 U 的背包。第 i 件物品的重量是 w[i],体积是 u[i],价值是 v[i]。求解将哪些物品装入背包可使价值总和最大。 (1) 0/1背包的表示方法 费用加了一维,只需把状态也加一维。 1. 状态表示:设 f[i][c][u]为前 i 件物品付出两种代价分别为 c 和 u 时可以获得的最大价值。 ìf[i-1][c][u]2. 状态转移方程:f[i][c][u]=maxíîf[i-1][c-w[i]][u-u[i]]+v[i] 当然,为了节省空间,可以把 i 去掉。 3. 一个启示:当发现由熟悉的动态规划题目变形而来的题目时,在原来的状态中加一维以满足新的限制,这是一种比较通用的方法。 (2) 限制物品总个数的0/1背包 【问题描述】有 n 件物品和一个容量为 C 背包。第 i 件物品的重量是 w[i],价值是 v[i]。现在要求转入背包的物品个数不超过 M。求解将哪些物品装入背包可使价值总和最大。 只需把问题变一下——有 N 件物品和一个容量为 C、容积为 M 的背包。第 i 件物品的重量是 w[i],体积是1,价值是 v[i]。求解将哪些物品装入背包可使价值总和最大。 把最大个数看做一种容积就可以了。 (3) 二维费用的完全背包和多重背包问题 循环时仍然按照完全背包(顺序循环)和多重背包(分割)的方法操作,只不过比完全背包和多重背包多了一维。 (4) 二维费用背包的另一种解法 把背包的容量和费用看作一个复数。详见《背包九讲》。
|