#include "stdio.h"
#include <cstdlib>
struct stone
{
int name
int weight_t//物品的重量
float benefit//物品的价值
//float b
}
//按物品的效益排序
void sort(stone *data,int num)
{
//仅剩一个元素时排序完毕
if(num<1)
return
int low=0,high=num
stone key_s=data[low]//取数组的第一个作为关键字
float key=(float)key_s.benefit/key_s.weight
int empty=low//目标位置初始位置为low指向的位置
while(low<high)
{
if(low==empty)//后面的指针向前走
{
//找到比关键字小的元素把它移到low指向的位置
while((data[high].benefit/data[high].weight<key)&&(high>low))
{
high--
}
if(data[high].benefit/data[high].weight>=key)
{
data[low]=data[high]
empty=high
}
}
else if(high==empty)//前面的指针向后走
{
//找到比关键字大的元素把它移到high指向的位置
while((data[low].benefit/data[low].weight>=key)&&(low<high))
{
low++
}
if(data[low].benefit/data[low].weight<key)
{
data[high]=data[low]
empty=low
}
}
}
data[empty]=key_s//把关键字放到划分完毕后两部分的中间位置
//关键字前面的数列继续递推
if(empty>1)
sort(data,empty-1)
//关键字后面的数列继续递推
if(num-empty-1>0)
sort(data+empty+1,num-empty-1)
}
//输入物品的信息
void inputstone(stone *bag,int num)
{
for(int i=0i<numi++)
{
bag[i].name=i+1//物品的名字
printf("请输入第%d号物品的重量:",i+1)
scanf("%d",&bag[i].weight)
if (bag[i].weight<=0)
{printf("物品的重量必须大于0!\n")}
printf("请输入第%d号物品的价值:",i+1)
scanf("%f",bag[i].benefit)
if (bag[i].benefit<=0)
{printf("物品的价值必须大于0!\n")}
bag[i].weight_t=bag[i].weight
}
}
//主函数
int main(int argc, char* argv[])
{ int i
int num=0//放入物品的数量
int weight=0//背包可容纳的重量
float benefit=0//总效益
stone *bag//物品
/////输入背包可容纳的重量
do
{
printf("请输入背包可容纳的重量:")
scanf("%d",&weight)
if (weight<=0)
printf("背包可容纳的重量必须大于0!\n")
}while(weight<=0)
//输入物品种类
do
{
printf("请输入物品的数量:")
scanf("%d",&num)
if (num<=0)
printf("物品数量必须大于0!\n")
}while(num<=0)
bag=new stone[num]//物品数组
inputstone(bag,num)//输入物品的信息
sort(bag,num-1)//按单位效益排序
for(i=0i<num&&weight>0i++)
{
stone *temp=bag+i
if(weight>=temp->weight)
{
weight-=temp->weight
temp->weight=0
benefit+=temp->benefit
continue
}
else
{
temp->weight-=weight
weight=0
benefit+=(temp->benefit*(1-(float)temp->weight/temp->weight_t))
break
}
}
////////输出结果//////////
printf("物品种类 放入的比例 每单位效益 ")
for(i=0i<numi++)
{
stone *temp=bag+i
printf("%d类物品",temp->name)
printf("\t\t%.2f\t\t",(temp->weight_t-temp->weight)/(float)temp->weight_t)
printf(" %.4f\n",temp->benefit/(float)temp->weight_t)
}
printf("总效益:%.2f",benefit)
delete bag
getchar()
system("PAUSE")
return EXIT_SUCCESS
return 0
}
背包问题小结- []2006-07-28做到背包问题觉得很有意思，写写看看。
完全背包问题可以用贪心算法。
代码如下：
program bag1
const maxn=10
var
goods:array[1..maxn,1..3] of integer
s:array[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]:=1x:=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:array[1..maxn,1..3] of integer{原始数据}
s:array[1..maxn] of integer{当前的状态}
r:array[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 mn>m 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]:=jtry(n+1)goods[n,3]:=0end
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求和十效率降低。不过这确实是一种很新颖的算法。
