问题描述：背包容量30，物品1、2、3、4、5的重量分别是3,20，5,10,5，其价值分别是8,50,12,21,10，要使装入背包的物品的总价值最大，如何进行装入。
这是我未优化的代码：
程序代码：#include <stdio.h>
#include <stdlib.h>
int n=5;
int w[5]={3,20,5,10,5};
int v[5]={8,50,12,21,10};
int c=30;
int now_w=0;//当前总重量
int now_v=0;//当前总价值
int max_v=0;//最大总价值
int x[10];//记录物品的选择情况
int best_x[10];//记录物品的最优选择情况
int sum=0;//记录解空间树的分支数
void backbag(int i){
if(i>=n){
int j;
if(now_v>max_v){
max_v=now_v;
for(j=0;j<n;j++)
best_x[j]=x[j];
}
}
else{
if(now_w+w[i]<=c){
sum++;
now_w+=w[i];
now_v+=v[i];
x[i]=1;
backbag(i+1);
now_w-=w[i];
now_v-=v[i];
}
x[i]=0;
sum++;
backbag(i+1);
}
}
void print(){
int i=0;
for(i=0;i<n;i++){
if(best_x[i]==1)
printf("%d,%d\n",w[i],v[i]);
}
}
int main()
{
backbag(0);
printf("选中的物品的重量和价值是：\n");
print();
printf("最大价值：%d",max_v);
printf("\n解空间树的分支数：%d",sum);
return 0;
}
其运行结果：
只有本站会员才能查看附件，请 登录
这是加入了剪枝函数的代码：
程序代码：#include <stdio.h>
#include <stdlib.h>
int n=5;
int w[5]={3,20,5,10,5};
int v[5]={8,50,12,21,10};
int c=30;
int remain_v=0;//当前剩余物品的总价值
int now_w=0;//当前总重量
int now_v=0;//当前总价值
int max_v=0;//最大总价值
int x[10];//记录物品的选择情况
int best_x[10];//记录物品的最优选择情况
int sum=0;//记录解空间树的分支数
int Bound(int i)
{
while(i<n)
{
remain_v+=v[i];
i++;
}
return remain_v+now_v;
}
void backbag(int i){
if(i>=n){
int j;
if(now_v>=max_v)
{
max_v=now_v;
for(j=0;j<n;j++)
best_x[j]=x[j];
}
}
if(now_w+w[i]<=c)
{
sum++;
now_w+=w[i];
now_v+=v[i];
x[i]=1;
backbag(i+1);
now_w-=w[i];
now_v-=v[i];
}
if(Bound(i+1)>max_v)
{
sum++;
x[i]=0;
backbag(i+1);
}
}
void print(){
int i=0;
for(i=0;i<n;i++){
if(best_x[i]==1)
printf("%d,%d\n",w[i],v[i]);
}
}
int main()
{
backbag(0);
printf("选中的物品的重量和价值是：\n");
print();
printf("最大价值：%d",max_v);
printf("\n解空间树的分支数：%d",sum);
return 0;
}
这是运行结果：
只有本站会员才能查看附件，请 登录