01背包问题—–回溯法的解决方案



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;
}
http://www.2cto.com/kf/201311/256131.html