求完全背包问题的代码(C语言或C++版)或算法
背包问题小结- []2006-07-28
做到背包问题觉得很有意思,写写看看。
完全背包问题可以用贪心算法。
代码如下:
program bag1;
const maxn=10;
var
goods:arr***[1..maxn,1..3] of integer;
s:arr***[1..maxn] of real;
i,j:integer;
m,n:integer;
y:integer;
x:real;
function max:integer;
var m:real;
i,j:integer;
begin
m:=0;
for i:=1 to n do
if (goods[i,3]=0) and (m max:=j;
end;
procedure choose;
var i,j:integer;
begin
while y begin
if y begin
i:=max;
if m=y+goods[i,1] then begin goods[i,3]:=1;x:=x+goods[i,2];y:=y+goods[i,1];end else
begin
x:=x+(m-y)*s[i];
y:=m;
end;
end;
end;
end;
begin
fillchar(goods,sizeof(goods),0);
assign(input,'b.txt');
reset(input);
readln(m,n);
for j:=1 to n do
read(goods[j,1]);
readln;
for j:=1 to n do
read(goods[j,2]);
for j:=1 to n do
s[j]:=goods[j,2]/goods[j,1];
close(input);
choose;
writeln(x:5:2);
end.
编得不是很好 ^-^ 献丑了。
我来说说0/1背包问题。
状态:当前物品n
算符:j=0(当前物品不放入背包) 或 j=1(当前物品放入背包)
这就很好说了,还是把yes函数一改,问题OK了。
代码如下:
program bag2;
const maxn=10;
var i:integer;
goods:arr***[1..maxn,1..3] of integer;{原始数据}
s:arr***[1..maxn] of integer;{当前的状态}
r:arr***[1..maxn] of integer;{当前的总质量}
m:integer;{背包容量}
max:integer;{物品个数}
procedure try(n:integer);
var j:integer;
{function yes:boolean;
var k:integer;
t:integer;
mn:integer;
begin
mn:=0;
t:=goods[n,3];
goods[n,3]:=j;
for k:=1 to n do
if goods[k,3]=1 then inc(mn,goods[k,1]);
goods[n,3]:=t;
if mnm then yes:=false else yes:=true;
end;}
begin
if n=max+1 then begin if x for i:=1 to max do s[i]:=goods[i,3]; {保存***解}end
end else
begin
if r[n-1]m then exit;{已超过背包总容量}
for j:=1 downto 0 do
begin
if j=1 then r[n]:=r[n-1]+goods[n,1];
if j=0 then r[n]:=r[n]-goods[n,1];
if {yes}r[n]=m then begin goods[n,3]:=j;try(n+1);goods[n,3]:=0;end
end;
end;
end;
begin
assign(input,'b.txt');
reset(input);
readln(m,max);
for i:=1 to max do
read(goods[i,1]);
readln;
for i:=1 to max do
read(goods[i,2]);
close(input);
try(1);
for i:=1 to 7 do
write(s[i]:3);
writeln;
writeln(x);
end.
用yes 函数要从头到当前求已装入背包物品的总质量,时间效率不高。所以我们引入r[n]数组来记录当前背包总质量(很好用!)注意用r[n-1]m来做剪枝,以再次提高时间效率。
DC跟我说可以用二进制解此类问题。我觉得很有创意,也说说。比如8个物品,每个物品有0/1两种状态所以我们从(00000000)(二进制 )到(11111111)(二进制)循环即可。然后在分离十进制数对应起来即可。但在实际的操作中发现效率比回溯还低,我想有两方面的原因:1、显而易见,不可能做剪枝。2、每一次结果都要从1到8求和十效率降低。不过这确实是一种很新颖的算法。
完全背包的简单有效的优化
完全背包问题有一个很简单有效的优化,是这样的:若两件物品i、j满足c[i]=c[j]且w[i]=w[j],则将物品j去掉,不用考虑。这个优化的正确性显然:任何情况下都可将价值小费用高得j换成物美价廉的i,得到至少不会更差的方案。对于随机生成的数据,这个方法往往会大大减少物品的件数,从而加快速度。然而这个并不能改善最坏情况的复杂度,因为有可能特别设计的数据可以一件物品也去不掉。这个优化可以简单的O(N^2)地实现,一般都可以承受。
另外,针对背包问题而言,比较不错的一种方法是:首先将费用大于V的物品去掉,然后使用类似计数排序的做法,计算出费用相同的物品中价值***的是哪个,可以O(V+N)地完成这个优化。这个不太重要的过程就不给出伪代码了,希望你能独立思考写出伪代码或程序。
既然01背包问题是最基本的背包问题,那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是,考虑到第i种物品最多选V/c件,于是可以把第i种物品转化为V/c件费用为c[I]及价值w[I]的物品,然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度,但这毕竟给了我们将完全背包问题转化为01背包问题的思路:将一种物品拆成多件物品。
更高效的转化方法是:把第i种物品拆成费用为c*2^k、价值为w*2^k的若干件物品,其中k满足0=k=log2(V/c)+1。这是二进制的思想,因为不管***策略选几件第i种物品,总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log2(V/c))件物品,是一个很大的改进。
背包问题(完全背包)
1.矩阵链乘法
2.投资组合问题
3.完全背包问题
4.01背包问题
5.最长公共子序列
一个背包,可以放入n种物品,物品j的重量和价值分别为 ,如果背包的***重量限制是b,怎么样选择放入背包的物品以使得背包的总价值***?
组合优化问题,设 表示装入背包的第j个物品的数量,解可以表示为 。那么目标函数和约束条件是:
如果组合优化问题的目标函数和约束条件都是线性函数,称为线性规划。如果线性规划问题的变量 都是非负整数,则称为整数规划问题。背包问题就是整数规划问题。限制所有的 时称为0-1背包
子问题的界定(就是靠什么来划分子问题):由参数k和y界定
k:考虑对物品1,2,3,...,k的选择。
y:表示背包总重
子问题计算顺序:k=1,2,...,k,对给定的k,y=1,2,...,b
:装前k个物品,重量不超过y时的背包***值。
包含两种情况:不装第k种物品或至少装一件第k种物品。
对 的解释:装一件第k种物品后,***的解法仍然是在前k个物品进行选择,仍有可能再选入1件第k种物品。
对边界条件:
:即只用***种物品背包重量限制为y的***价值,为了保证背包不超重,***种物品至多能装 个,因为背包价值为
有些 那么通过设置为负无穷,在选择过程中抛弃掉为负的情况。
标记函数:用来追踪解
按照递推公式:以k=2为例子,简单演算如下:
依次类推,可得备忘录表:
标记函数的备忘录:
物品受限背包 :第i种物品最多用 个
0-1背包问题 :
多背包 :m个背包,背包 装入***重量 在满足所有背包重量约束下使物品价值***。
二维背包 :每件物品重量 和体积 ,背包总重不超过b,体积不超过V,使得物品价值***。
此问题是完全背包问题,即 一个物品可重复出现。
完全背包问题(C语言,pascal)
4.1 原始递归法
先看完全背包问题
一个旅行者有一个最多能用m公斤的背包,现在有n种物品,每件的重量分别是W1,W2,...,Wn,
每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多.
求旅行者能获得的***总价值。
本问题的数学模型如下:
设 f(x)表示重量不超过x公斤的***价值,
则 f(x)=max{f(x-i)+c[i]} 当x=w[i] 1=i=n
可使用递归法解决问题程序如下:
program knapsack04;
const maxm=200;maxn=30;
type ar=arr***[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
function f(x:integer):integer;
var i,t,m:integer;
begin
if x=0 then f:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x=w[i] then m:=f(x-i)+c[i];
if mt then t:=m;
end;
f:=t;
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
writeln(f(m));
end.
说明:当m不大时,编程很简单,但当m较大时,容易超时.
4.2 改进的递归法
改进的的递归法的思想还是以空间换时间,这只要将递归函数计算过程中的各个子函数的值保存起来,开辟一个
一维数组即可
程序如下:
program knapsack04;
const maxm=2000;maxn=30;
type ar=arr***[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
p:arr***[0..maxm] of integer;
function f(x:integer):integer;
var i,t,m:integer;
begin
if p[x]-1 then f:=p[x]
else
begin
if x=0 then p[x]:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x=w[i] then m:=f(i-w[i])+c[i];
if mt then t:=m;
end;
p[x]:=t;
end;
f:=p[x];
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
fillchar(p,sizeof(p),-1);
writeln(f(m));
end.
关于完全背包和完全背包问题详解的介绍到此就结束了,不知道你从中找到你需要的信息了吗 ?如果你还想了解更多这方面的信息,记得收藏关注本站。