你吧 原来的1-2-3号按照东西的价值重新排列现在的1-2-3对应原来的2-1-3了
所以 你输出的时候是按 1-2-3输出的话 就等于第一个是原来的X2 第二个是X1第三个是X3
而且你的冒泡排序用错了 只比较了 P[0]/K[0]和P[1]/K[1] P[1]/K[1]和P[2]/K[2]
周一我去学校帮你重新改改 我家的机器没有C++
周一晚上我会上传答案~我最近正好也要做算法的作业~
#include <stdio.h>
#include <math.h>
#define N 50
float find(float p[N],float w[N],float x[N] ,float M,int n) /*先放单位价值量大的物体，再考虑小的物体*/
{
int i
float maxprice
for (i = 0i <ni++)
x[i] = 0
i = 0
maxprice=0
while (i <n &&w[i] <M)
{
M=M-w[i]
x[i] =w[i]/* 表示放入数量 */
maxprice=maxprice+p[i]
x[n-1]=M
i++
}
if (i <n &&M>0)
{
maxprice=maxprice+p[i]*x[i]/w[i]
i++
}
return maxprice
}
int main()
{
int n,flag=1
float temp,M,w[N],p[N],x[N]
int a[N],b[N]
int k,j,l=0
printf(
背包问题小结- []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求和十效率降低。不过这确实是一种很新颖的算法。
