pascal 01背包和完全背包的区别

显示全部楼层 · 2010-4-2 17:20:39

背包是什么知道撒01背包是指每个物品只能用一次完全背包指的是每个物品都能无限使用没什么技巧，DP类的明确了状态后就写起来快了，写多了程序自然也就有经验了，有经验就能快速的推出状态，总之就是多写题程序的不同很简单完全背包for i:=1 to n do //枚举1-N的物品for j:=a to m do //枚举1-M的能背出来的范围
f[j]:=f[j] or f[j-a];01背包for i:=1 to n do //枚举1-N的物品for j:=m downto a do //枚举1-M的能背出来的范围
f[j]:=f[j] or f[j-a];注意，之前要先f[0]:=true；可以看出，区别只在第二个循环的正倒，F是一个布尔数组，F表示i这个数字能够被组合出来为什么循环的正倒会导致这样的区别呢？我们举个例子：假设我们现在组合出了3，现在讨论的物品体积是1，那么,即a=1, f[3]:=true;当正循环时当枚举到4的时候，f[4]=f[4] or f[4-1]=true，因为f[3]=true;当枚举到5的时候，f[5]=f[5] or f[5-1]=true，因为f[4]=true;显然，这个“1”会被无限的使用下去直到到达M的上限逆循环则相反 ----------------纯原创，求最佳···

千问 · 2010-4-2 17:20:39

慢慢领悟！像学奥数方法一样！01背包一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。完全背包问题一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn,每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多.

千问 · 2010-4-2 17:20:39

背包问题是一个经典的动态规划模型，容易描述，容易理解。背包问题可简单描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。01背包问题的特点是，每种物品仅有一件，可以选择放或不放。　　01背包问题描述：　　有N件物品和一个容量为V的背包。第i件物品的重量是c，价值是w。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。　　写出状态转移方程：　　f[v]=max{f[i-1][v], f[i-1][v-c]+w}　　f[v]:前i件物品恰放入一个容量为v的背包可以获得的最大价值　　f[i-1][v]:前i-1件物品……（同上），即不放入第i件物品的情况　　f[i-1][v-c]+w:放入第i件物品的情况，放入后的 f[v] 应该等于前 i-1 件物品在容量为 v-c 上的最大价值加上 w　　空间优化：　　f[v]=max{f[i-1][v], f[i-1][v-c]+w}　　观察黑色字体部分，发现二维数组完全可以用一维数组替代：　　f[v]=max{f[v], f[v-c]+w}　　程序怎么写？循环如何写？　　首先考虑如果所有的物品都能放进去，那一定就是最大价值，如果只能放进去 i （iw; --v)//逆序推能够保证 f[v-c] 保存的是状态是 f[i-1][v-c] ，也就是每个物品只被使用了一次；顺序的话 f[v-c] 保存的是 f[v-c] ，每个物品有可能被使用多次，也就是完全背包问题的解法。　　f[v]=max(f[v], f[v-c]+w)