求完全背包问题的代码(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.
关于完全背包和完全背包问题详解的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。