Question

pascal如何思考DP方程

动态规划里的DP方程怎么思考出来啊，顺便举几个例子哈！谢谢了

Answer 1

题目1：01背包
有N件物品和一个容量为V的背包。第i件物品的体积是c[i]，价值是w[i]。求如果选择哪些物品装入背包，使得价值总和最大。

1．状态的定义
（1）以f[I,j]表示前I种物品中任意取，容量不超过j时能得到的最大价值
（2）所求为f[n,v]
2．递推式
f[I,j]=Max{f[I-1,j],f[I-1,j-c[I]]+w[I]}
3．初值
f[0,j]=0 j=0~v
4．求解过程
for I:=1 to n do
for j:=0 to v do
if (j>=c[I]) and (f[I-1,j-c[I]]+w[I]>f[I-1,j]) then
f[I,j]:=f[I-1,j-c[I]]+w[I]
else f[I,j]:=f[I-1,j];
5．滚动数组优化，使空间由nv降为2v
c:=0;//已求得第c行
for I:=1 to n do begin//以f[c,j]表示f[I,j],以f[1-c,j]表示f[I-1,j]
c:=1-c;//已求得的为第1-c行
for j:=0 to v do
if (j>=c[I]) and (f[1-c,j-c[I]]+w[I]>f[1-c,j]) then
f[c,j]:=f[1-c,j-c[I]]+w[I]
else f[c,j]:=f[1-c,j];
end;
每次I循环不要省略小于c[I]的部分
6．一维优化，空间降为v
for I:=1 to n do
for j:=v downto c[I] do
if f[j-c[I]]+w[I]>f[j]) then
f[j]:=f[j-c[I]]+w[I];
//else f[j]:=f[j];
7．另一种状态定义
（1）以f[I,j]表示前I种物品中任意取，容量恰好为j时能得到的最大价值
（2）所求为f[n,v],f[n,v-1],…,f[n,0]中的最大者
（3）初值为：f[0,0]=0,f[0,j]=-∞,其中j=1~v
其余一样
8．如果是求在n种物品中，任意取，体积恰好为V时的最大价值，则必须使用第二种定义了。

题目2：完全背包
有N种物品（每种物品数量无限），和一个容量为V的背包。第i种物品的体积是c[i]，价值是w[i]。求如果选择哪些物品装入背包，使得价值总和最大。
法1：O(v*∑(v/c[I]))
以f[I,j]表示在前I种物品中任意取，容量不超过j时的最大价值。
F[I,j]=Max{f[I-1,j-k*c[I]]+k*w[I]} k=0~j/c[I]

法2：将第I种物品转化为v/c[I]件体积和价格相同的物品，问题变为01背包。
但复杂度同法1。
法3：将第I种物品转化为体积c[i]*2k[I]、价值为w[i]*2k[I]的若干件物品。其中k[I]=0~P[I]，P[I]满足2P[I]*c[I]<=v，即P[I]<=log2(v/c[I])

法4：f[I,j]表示在前I种物品中任意取，容量不超过j时的最大价值。O(vn)
For I:=1 to n do
For j:=0 to v do begin
F[I,j]:=f[I-1,j];
If (j>=c[I]) and (f[I,j-c[I]]+w[I]>f[I,j]) then
F[I,j]:=f[I,j-c[I]]+w[I];
End;
或一维的：
for I:=1 to n do
for j:=c[I] to v do
if f[j]<f[j-c[I]]+w[I] then
f[j]:=f[j-c[I]]+w[I];

这段程序与01背包相比，只有一点不同，f[I,j-c[I]]和f[I-1,j-c[I]]。
在01背包中f[I,j]与f[I-1,j-c[I]]有关，表示前I个物品与前I-1个物品有关，因为该物品只能选一次，不能多选。
在完全背包中，f[I,j]与f[I,j-c[I]]有关，因为第I种物品可以多次选，因此正需要一个可能已选入第i种物品的子结果f[I,j-c[i]]。
当使用一维时，在01背包中，只能使j循环从大到小，从小到大时，会选入第I个物品多次的。在完全背包中，则要使j循环从小到大，使得第I种物品可以多次考虑。

题目3：多重背包
有N种物品，和一个容量为V的背包。第i种物品的数量有n[I]个，体积是c[i]，价值是w[i]。求如果选择哪些物品装入背包，使得价值总和最大。
法1：复杂度O(v*∑n[i])
第i种物品化为n[I]个单独物品，使用标准的01背包求解，复杂度O(v*∑n[i])。
法2：复杂度O(V*∑log n[i])
将第I物品转化成体积c[i]*2k[I]、价值为w[i]*2k[I]的若干件物品，
例1：某种物品有9件，每件体积为c[I]，价值为w[I]，则将此种物品变为以下4件物品：
物品1：体积1*c[I]，价值1*w[I]； 物品2：体积2*c[I]，价值2*w[I]；
物品3：体积4*c[I]，价值4*w[I]； 物品4：体积2*c[I]，价值2*w[I]；
例2：某种物品有44件，每件体积为c[I]，价值为w[I]，则将此种物品变为以下6件物品：
物品1：体积1*c[I]，价值1*w[I]； 物品2：体积2*c[I]，价值2*w[I]；
物品3：体积4*c[I]，价值4*w[I]； 物品4：体积8*c[I]，价值2*w[I]；
物品5：体积16*c[I]，价值16*w[I]； 物品6：体积13*c[I]，价值13*w[I]；
这样，无论这种物品取多少件，都可以使用以上转换得到的各件物品的选择与否来组合得到。最终通过标准的01背包问题来求解。复杂度O(V*∑log n[i])。

题目4：混合背包
将所有多重背包化为多个01背包，然后：
for i=1..N
if 第I种物品是01背包
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
else if 第I种物品是完全背包
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]}

题目5二维费用的背包
问题：有n件物品，第I件物品的体积为v[I]，重量为g[I]，价值为w[I]。求体积不超过X，重量不超过y时价值的最大值。
费用增加一维，状态也增加一维。

有时，“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取M件物品。这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为1，可以付出的最大件数费用为M。
比如挤牛奶。

题目6分组的背包问题
问题
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
算法
这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设f[k][j]表示前k组物品花费费用j能取得的最大权值，则有f[k][j]=max{f[k-1][j],f[k-1][v-c[i]]+w[i]|物品i属于第k组}。
使用一维数组的伪代码如下：
for 所有的组k
for 所有的i属于组k
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]}

Answer 2

这要自己在纸上列一个表，写出目前条件与符合的可能性的关系。。
例子嘛，，，背包问题很经典的啊！！！

Answer 3

现在看来，除了多做题练习，多看书总结，别没什么好方法。