01背包问题-----回溯法的解决方案
01背包问题是个经典的动态规划问题，但是也可以用回溯法来解决。只是这是找一个子树而不是一个全部树元素的排列。#include<iostream>
using namespace std;
#define MAX 1024
int C=7;//最大重量
int N=4;//包个数
int value[MAX];//记录每个包的价值
int weight[MAX];//记录每个包的重量
int currentValue=0;//当前的价值
int currentWeight=0;//当前的重量
int maxValue=0;//记录最大价值
int tempRecord[MAX];//记录选中的包编号
int maxRecord[MAX];//记录当取最大价值时的选中的包编号
/*
* 设置tempcount和maxcount是我们只是找一棵子树。每次找的个数也许都不一样，这就是tempcount的原因。
* 为了正确的记录当取到最大价值时的节点编号，我们用了maxcount这个记录变量。
*/
int tempcount;//记录每次选中包的个数
int maxcount;//记录最大价值时选中的包个数
void swap(int& a,int& b)
{
int temp=a;
a=b;
b=temp;
}
void init()
{
/* 测试数据一*/
value[1]=9;
value[2]=10;
value[3]=7;
value[4]=4;
weight[1]=3;
weight[2]=5;
weight[3]=2;
weight[4]=1;
/* 测试数据二
weight[1]=1;
weight[2]=4;
weight[3]=2;
weight[4]=3;
value[1]=2;
value[2]=1;
value[3]=4;
value[4]=3;
*/
int i;
for(i=1;i<=N;i++)
tempRecord[i]=i;
}
void backtrace(int t)
{
int i;
if(t<=N)
{
for(i=t;i<=N;i++)//排列
{
swap(tempRecord[i],tempRecord[t]);
if(weight[tempRecord[t]]<=C-currentWeight)
{
tempcount++;
currentWeight+=weight[tempRecord[t]];
currentValue+=value[tempRecord[t]];
backtrace(t+1);
tempcount--;
currentWeight-=weight[tempRecord[t]];
currentValue-=value[tempRecord[t]];
}
swap(tempRecord[i],tempRecord[t]);
}
}
if(t>N||i>N)
/*
设置i>N的原因是我们只是找一个子树（子序列），而不是一个完整的树。所以很有可能我们找不到第t层的节点（第t个节点）。
但是我们要一直搜索到最后一个节点知道超过N，那么我们要对这种情况进行判断。
当然t>N是肯定要执行的。
*/
{
if(currentValue>maxValue)
{
maxValue=currentValue;
maxcount=tempcount;
for(i=1;i<=tempcount;i++)
{
maxRecord[i]=tempRecord[i];
}
}
}
}
void main()
{
init();
backtrace(1);
int i;
cout<<"包的价值为:";
for(i=1;i<=N;i++)
{
cout<<"value["<<i<<"]="<<value[i]<<" ";
}
cout<<endl;
cout<<"包的重量为:";
for(i=1;i<=N;i++)
{
cout<<"weight["<<i<<"]="<<weight[i]<<" ";
}
cout<<endl;
cout<<"最大价值为: "<<maxValue<<endl;
cout<<"选中的包个数为 :"<<maxcount<<endl;
cout<<"选中的包编号分别为:";
for(i=1;i<=maxcount;i++)
cout<<maxRecord[i]<<" ";
cout<<endl;
}
补充：软件开发 , C++ ,
