求完全背包问题代码 物品有n种 每种无限个 一个背包 求在容量限定的条件下求最大

求完全背包问题代码 物品有n种 每种无限个 一个背包 求在容量限定的条件下求最大

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.追问我想要c++代码

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

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