背包有件物品和一个容量为的第费用是ci价值wi求解

1、012008-04-05ivi012008-04-05ivii-1vi 先考虑上面讲的基本思路如何实现，肯定是有一个主循环 i=1.N fiv时（ifv时） - -for for 其 中 的 fv=maxfv,fv-ci 一 句 恰 就 相 当 于的 转 移 方 程fiv=maxfi-1v,fi-1v-ci ， 因为现在的 fv-ci 就相当于原来的 fi-1v-civfiv由 其 中 的 fv=maxfv,fv-ci 一 句 恰 就 相 当 于的 转 移 方 程fiv=maxfi-1v,fi-1v-ci ， 因为现在的 fv-ci 就相当于原来的 fi-1v-civfiv由 P02:wi。求

2、解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总01fiviv最大权值。 仍然可以按照每种物品不同的策略写出状态转移方程， 像这样： fiv=maxfi-1v-k*ci+k*wi|0=k*ci= v01O(N*V)个状态需要求解，但求解每个状态的时间则不是常数了， 求解状态 fiv的时间是完全背包问题有一个很简单有效的优化，是这样的：若两件物品 i、j 满足 ci=cj 改进。 有更优的O(VN)的算法。*O(VN)的算法这个算法使用一维数组，先看伪fori=1.Nforv=0.Vfv=maxfv,fv-你会发现，这个伪代码与 P01 的伪代码只有 v 的循环次序不同而已。为

3、什么这样一改就可行呢？首先想想为什么 P01 中要按照 v=V.0 的逆序来循环这是因为要保证第 i 次循环中的状次，保证在考虑“选入第 i 件物品”这件策略时，依据的是一个绝无已经选入第 i 件物品的选一件第 i 种物品” 这种策略时， 却正需要一个可能已选入第 i 种物品的子结果 P03:对于第i物品有ni+1略：取0件，取1取n i件。令对于第i物品有ni+1略：取0件，取1取n i件。令fiv表示前i物品恰放入一个容量为 vfiv=maxfi-1v-品，则得到了物品数为ni01O(V*ni)但的，i1,2,4,.,2(k-1),ni-2k+1，kni-2k+10ni13，就将这种物品分

4、成系数分别也能保证对于 0.ni这样就将第i种物品分成了O(logni)O(V*logO(VN)多重背包问题同样有 看到了将一个算法的复杂度由O(V*niO(V*logni了存在应用超出NOIPO(VNP04:P01、P02、P03（01，有的物品P01P02for ifP01、P02、P03（01，有的物品P01P02for ifi01for elseif 第ifor O(VN)的解法：遇到多重背 P05:2v和u时 可 获 得 的 最 大 价 值 。 状 态 转 移 方 程 就 是 ： vu有时，“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取Mv和u时 可 获 得 的 最 大

5、价 值 。 状 态 转 移 方 程 就 是 ： vu有时，“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取M。P06:设 fkv k v forfor 所有的ifor P07P07:jfor P07P07:j个物品的物品组，其中费用为 ci+k 的物品的价值为 fk+wi。也就是说原来指数级的DP，DP，P08:h，当分配给它的费用为vh(v)一个费用为c 价值为w 的物品，如果它是 01 背包中的物品，那么把它看成泛化物品，它就是除了 h(c)=w 其它函数值都为 0 的一个完全背包中的物品那么它可以看成这nh(v)=v/c*wvch0.Vv，vhl，要用给定的费用从这两个泛化物品

6、中得到最大的价值，怎么求呢？事实上，对于一个给定的费用 v，只需枚举将这个费用如何分配给两个泛化物品就可f(v)=maxh(k)+ l(v-k)|0=k=v。可以看到，fh0.Vv，vhl，要用给定的费用从这两个泛化物品中得到最大的价值，怎么求呢？事实上，对于一个给定的费用 v，只需枚举将这个费用如何分配给两个泛化物品就可f(v)=maxh(k)+ l(v-k)|0=k=v。可以看到，fhl由此可以定义泛化物品的 和： hlf 满足O(V2)。例如 。的SchemenoiPOI。P09:组 gi vgiv=0 表示推出 fiv 的值时是采用了方程的前一项P09:组 gi vgiv=0 表示推出 fiv 的值时是采用了方程的前一项（ 1v，giv未选第 ifNVi个物品。那么输出方案的伪代码可以这