完全背包问题求价值总和最小

答案:2 悬赏:70 手机版

解决时间 2021-03-20 09:32

提问者网友：人生佛魔见
2021-03-19 12:39

完全背包问题求价值总和最小

最佳答案

五星知识达人网友：像个废品
2021-03-19 14:09

01背包题目有N种物品和一个容量为V的背包，每种物品都有1件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。思路：此方法是动规的题目，动态转移方程不难求出：f[x]:=max(f[x],f[x-w]+c); 但是循环需要反向更新为什么呢，因为f[i,x]是由f[i-1,x-w]推导出来的换句话说，如果把反向改成顺序更新的话，f[i,x]就是由f[i,x-w]推知，与本题题意不符，但却是完全背包的循环方式 For i:=1 to n do for x:=m downto w do 意思是不超过x公斤的背包可获得的最大价值代码如下 var f:Array[1..10000]of longint; j,i,m,n,w,c,max1:longint; function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end; begin readln(m,n);//容量是m，有n种物品 for i:=1 to n do begin readln(w,c); for j:=m downto w do f[j]:=max(f[j-w]+c,f[j]); end; max1:=0; for i:=1 to m do if f[i]>max1 then max1:=f[i]; writeln(max1); End. 。。。。。。。。。。。。我是分割线。。。。。。。。。。。。。。完全背包题目有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。思路：此题目与01背包非常相似，但不同之处在于01背包每件物品只能取一次，而完全背包每件物品可取无限次。如果我们把这道题目转换成01背包的话，循环仅需变成顺向更新就行了，动态转移方程不变代码如下： var f:Array[1..10000]of longint; j,i,m,n,w,c,max1:longint; function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end; begin readln(m,n);//容量是m，有n种物品 for i:=1 to n do begin readln(w,c); for j:=w to m do f[j]:=max(f[j-w]+c,f[j]); end; max1:=0; for i:=1 to m do if f[i]>max1 then max1:=f[i]; writeln(max1); End. 。。。。。。。。。。。。我是分割线。。。。。。。。。。。。。。多重背包题目有N种物品和一个容量为V的背包，每种物品都有n件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。思路：此题与完全背包十分相似，基本的方程只需将完全背包的改一下即可，因为第i种物品有n[i+1]种策略，取0件，一件，2件…n[i]件则方程为f[i,x]:=max(f[i-1,v-k*w[i]]+k*c[i],f[i,x]); 程序如下： Var v,w,s,f:Array[1..1000]of longint; I,j,k,n,m:longint; function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end; Begin Readln(m,n); For i:=1 to n do readln(v[i],w[i],s[i]); For i:=1 to n do For j:=m downto 0 do For k:=0 to s[i] do Begin If j-k*v[i]<0 then break;//特殊情况 F[j]:=max(f[j],f[j-k*v[i]]+w[i]*k); End; Writeln(f[m]);//最优解 End. Ps:纯本人原创，切勿抄袭，在多重背包的思路中，由于i-1是值上一个阶段的决策，可省略，所以在代码中没有出现i-1.

全部回答

1楼网友：行雁书
2021-03-19 15:06

（一）二维表：完全背包算法: for i:=1 to n do for j:=1 to m do if j>w[i] then if f[i-1,j]>f[i,j-w[i]]+p[i] then f[i,j]:=f[i-1,j] else f[i,j]:=f[i,j-w[i]]+p[i] else f[i,j]:=f[i-1,j]; writeln(f[n,m]); 顺便给你个一维的对照（二）一维表 for i:=1 to n do for j:=w[i] to m do if f[j]

我要举报

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息