背包有关问题（DP、回溯）

背包问题（DP、回溯）

算法设计例题：背包问题（DP、回溯）

memory limit: 65536KB    time limit: 500MS

accept: 7    submit: 24

Description

Input

Output

Sample Input

Sample Output

#include"iostream"

#include"algorithm"
#include"map"
using namespace std ;
class Knapsack{
public :
    double c ;//Knapsack capacity
    int n ; // item numbers
    double w [1000] ;// Item weight array
    double p [1000] ;//item value array
    double  cw ;//current weight
    double cp ;// current value
    double bestp; // current best value
    double setdata ( )
    {
        cw = 0.0 ;
        cp = 0.0;
        bestp =0 ;
    }
    void backtrack(int i)
    {
        if ( i > n )
        {

             bestp = cp ;
            //  为什么不用和前一个进行比较就进行跟新呢？者主要得利域贪心算法的好处，。进入左子树时不需要计算上界，因为其上界以其父结点的上界相同
            return  ;//to Leaf node
        }
        //sort child tree
        if ( cw + w [i] <= c )
        {
            //into left child tree
            cw += w[i];
            cp+=p[i];
            backtrack( i + 1 );
            cw -= w [ i ] ;
            cp -= p[i] ;
        }
        if(bound( i+1 ) > bestp )
            backtrack( i + 1 ) ; //into light child tree
    }
    //calculate up bound
     double bound( int i )
    {
        //calculate up bound
        double cleft = c - cw ;//residual capacity
        double bound = cp ;
        //With items unit weight value decreasing order load items
        while ( i <= n && w[i] <= cleft )
        {
            cleft -= w[i];
            bound += p[i];
            i++;
        }
        //Backpack  being filled with
       if ( i <= n )
        {
            bound += p[i] / w[i]* cleft  ;
        }
        return bound ;
    }

};
int main()
{
    Knapsack kk ,kk_1 ;
    multimap< double ,int > m ;
    multimap<double ,int >::reverse_iterator t;
    int n;
    int T ;
    int j=1 ;
    cin>>T;
    while(T>0)
    {
        cin>>kk.n;
        cin>>kk.c;
        int i =1 ;
        while(i<=kk.n)
        {
            cin>>kk.w[i];
            cin>>kk.p[i];
            m.insert(pair<double,int >(kk.p[i]/kk.w[i],i));
            i++;
        }
        //sort the data
        n=kk.n;
        i =  1 ;
        t = m.rbegin();
        while(t!=m.rend())
        {
            kk_1.w[i] = kk.w[t->second];
            kk_1.p[i] = kk.p[t->second];
          //  cout<<":"<<kk_1.w[i]<<" "<<kk_1.p[i];
            i++;
            ++t;
        }
        m.clear();
        kk_1.c = kk.c ;
        kk_1.n = kk.n;
        kk_1.setdata();
        kk_1.backtrack(1);
        int b =kk_1.bestp;
        cout<<b<<endl;
        T--;
    }
    return 0 ;
}