＋设为首页 ＋添加到收藏夹
是这样的:
有一家加工电线的工厂，原材料是只有几种长度的电缆，如 4米长的1根,6米长的2根,7米长的1根等，但是要加工出来的长度却经常要发生变化，而且加工出来的结果还不都是同一种长度，如结果要求为 1.2米的2根,1.6米的一根,2.1米的一根等。欲求两个算法，一个是怎样最小浪费原材料才能产生结果，另一种是怎样取最少的原材料根数就能生产出结果。
如，最小浪费原材料的情况下，1.2x2+1.6x1=4.0 这样4米的原材料就达到了最小浪费，但是在要求使用最少的原材料时,就应该直接用那根7米的就行了。
这是一个真实的应用，他们要的结果可能有上百根，而且原材料的长度和结果的长度都不是固定的，我想知道应用什么样的算法可以解决这个问题，如果有示例程序当然更好了，谢谢！
背包问题
[问题描述]
在M件物品取出若干件放在空间为W的背包里，每件物品的重量为W1，W·2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。
注意：在本题中，所有的重量值均为整数。
[算法分析]：
对于背包问题，通常的处理方法是搜索。
用递归来完成搜索，算法设计如下：
function Make( i {处理到第i件物品} , j{剩余的空间为j}:integer) :integer;
初始时i=m , j=背包总容量
begin
if i:=0 then
Make:=0;
if j>=wi then (背包剩余空间可以放下物品 i )
r1:=Make(i-1,j-wi)+v[i]; (第i件物品放入所能得到的价值 )
r2:=Make(i-1,j) (第i件物品不放所能得到的价值 )
Make:=max{r1,r2}
end;
这个算法的时间复杂度是O(2^n)，我们可以做一些简单的优化。
由于本题中的所有物品的重量均为整数，经过几次的选择后背包的剩余空间可能会相等，在搜索中会重复计算这些结点，所以，如果我们把搜索过程中计算过的结点的值记录下来，以保证不重复计算的话，速度就会提高很多。这是简单的"以空间换时间"。
我们发现，由于这些计算过程中会出现重叠的结点，符合动态规划中子问题重叠的性质。
同时，可以看出如果通过第N次选择得到的是一个最优解的话，那么第N-1次选择的结果一定也是一个最优解。这符合动态规划中最优子问题的性质。
考虑用动态规划的方法来解决，这里的：
阶段是：在前N件物品中，选取若干件物品放入背包中；
状态是：在前N件物品中，选取若干件物品放入所剩空间为W的背包中的所能获得的最大价值；
决策是：第N件物品放或者不放；
由此可以写出动态转移方程：
我们用f[i,j]表示在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值
f[i,j]=max{f[i-1,j-Wi]+Pi (j>=Wi), f[i-1,j]}
这样，我们可以自底向上地得出在前M件物品中取出若干件放进背包能获得的最大价值，也就是f[m,w]
算法设计如下：
procedure Make;
begin
for i:=0 to w do
f[0,i]:=0;
for i:=1 to m do
for j:=0 to w do begin
f[i,j]:=f[i-1,j];
if (j>=w[i]) and (f[i-1,j-w[i]]+v[i]>f[i,j]) then
f[i,j]:=f[i-1,j-w[i]]+v[i];
end;
writeln(f[m,wt]);
end;
由于是用了一个二重循环，这个算法的时间复杂度是O，在这一点上好像是矛盾的。
事实上，由于我们定下的前提是：所有的结点都没有重叠。也就是说，任意N件物品的重量相加都不能相等，而所有物品的重量又都是整数，那末这个时候W的最小值是：1+2+2^2+2^3+……+2^n-1=2^n -1
此时n*w>2^n，动态规划比搜索还要慢~~|||||||所以，其实背包的总容量W和重叠的结点的个数是有关的。
考虑能不能不计算那些多余的结点……
那么换一种状态的表示方式：
状态是：在前N件物品中，选取若干件物品放入所占空间为W的背包中的所能获得的最大价值；
阶段和决策：同上；
状态转移方程是：
f[i,j]=max{f[i-1,j-Wi]+Pi (j+Wi<=背包总容量), f[i-1,j]}
这样，我们可以得出在前M件物品中取出若干件放进背包在所占空间不同的状态下能获得的最大价值，在其中搜索出最大的一个就是题目要求的解。
算法设计如下：
procedure make;
begin
f[0,wt]:=0;
for i:=1 to n do
for j:=0 to w (背包总容量) do
if f[i-1,j]未被赋过值 then
continue
else
f[i,j]:=max{f[i-1,j+Wi]+Pi , f[i-1,j]};
最大价值：=max{f[n,j]}
j:=1 to w
end;
