问题描述
给定n种物品和一背包。物品i的重量为wi，其价值为vi， 背包容量为c。问应如何选择装入背包中的物品，使得背入背包的物品的总价值最大？
完整代码
#include "stdafx.h"
int n
;
int c
;
int bestp
;
int p
[20],w
[20];
int x
[20],bestx
[20];
int Bound(int i
, int cp
,int cw
){
int cleft
=c
-cw
;
int b
=cp
;
while(i
<=n
&& w
[i
]<cleft
)
{
cleft
-=w
[i
];
b
+=p
[i
];
i
++;
}
if(i
<=n
){
b
+=p
[i
]*cleft
/w
[i
];
return b
;
}
}
void Backtrack(int i
,int cp
,int cw
){
if(i
>n
){
if(cp
>bestp
){
bestp
=cp
;
for(i
=1;i
<=n
;i
++){
bestx
[i
]=x
[i
];
}
}
return;
}
if(cw
+w
[i
]<=c
){
x
[i
]=1;
cw
+=w
[i
];
cp
+=p
[i
];
Backtrack(i
+1,cp
,cw
);
cw
-=w
[i
];
cp
-=p
[i
];
}
if(Bound(i
+1,cp
,cw
)>bestp
){
x
[i
]=0;
Backtrack(i
+1,cp
,cw
);
}
}
int main(int argc
, char* argv
[])
{
int i
;
printf("请输入物品的数量：\n");
scanf("%d",&n
);
printf("请输入每个物品的重量和价值：\n");
for(i
=1;i
<=n
;i
++) {
scanf("%d%d",&w
[i
],&p
[i
]);
}
printf("请输入背包的容量：\n");
scanf("%d",&c
);
Backtrack(1,0,0);
printf("最大价值为:\n%d",bestp
);
printf("\n最优解为:\n");
for(i
=1;i
<=n
;i
++)
{
printf("%d ",bestx
[i
]);
}
printf("\n");
return 0;
}
测试
**测试过程：**运行程序，根据提示输入物品的数量，每个物品的重量和价值以及背包的容量，回车后系统显示最大的价值即最优值和最优解。
问题讨论
**讨论时间复杂度：**在最坏的情况下，所搜索的结果是一个满二叉树，此时相当于采用的就是穷举法，时间复杂度为，而每次决定是否要讲n个物品放入背包都要进行比较，这一步的时间复杂度为n，所以最坏情况下时间复杂度为。
