pascal如何思考DP方程动态规划里的DP方程怎么思考出来啊,顺便举几个例子哈!谢谢了
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/27 02:08:37
pascal如何思考DP方程动态规划里的DP方程怎么思考出来啊,顺便举几个例子哈!谢谢了
pascal如何思考DP方程
动态规划里的DP方程怎么思考出来啊,顺便举几个例子哈!谢谢了
pascal如何思考DP方程动态规划里的DP方程怎么思考出来啊,顺便举几个例子哈!谢谢了
题目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
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]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]