编辑代码

#include<bits/stdc++.h>
using namespace std;

class Knap
{
    friend int Knapsack(int *, int *, int, int);
    private:    
        int Bound(int i);             //计算上界
        void Backtrack(int i);
        int c;                //背包容量
        int n;                  //物品数
        int *w;               //物品重量数组
        int *p;               //物品价值数组
        int *number;            //排序后的编号情况
        bool *select;           //用来记录物品的选择情况
        int cw;               //当前重量
        int cp;               //当前价值
        int bestp;            //当前最优价值
};
void Knap::Backtrack(int i)
{
    static int k = 1;
    if(i > n)  //到达叶节点
    {
        bestp = cp;
        cout<<"第"<<k++<<"次到达叶节点,得到的最优价值为:"<<bestp<<endl;
        cout<<"此次物品选择情况为:"<<endl;
        for(int i=1; i<=n; i++)
        {
            if(select[i]==true) cout<<"选择物品"<<number[i]<<": 重量"<<w[i]<<" 价值"<<p[i]<<endl;
        }
        return ;
    }
    if(cw + w[i] <= c)  //进入左子树
    {
        cout<<"进入左子树深入一层,将到达第"<<i+1<<"层"<<endl;
        cw += w[i];
        cp += p[i];
        select[i] = true;
        Backtrack(i+1);
        cout<<"从左子树回溯一层,将到达第"<<i<<"层"<<endl;
        select[i] = false;
        cw -= w[i];
        cp -= p[i];
    }
    else cout<<"此时: cw:"<<cw<<" w[i]:"<<w[i]<<"   则cw+w[i]>c,不满足约束条件,无法继续向左,尝试向右"<<endl;
    if(Bound(i+1) > bestp)      //进入右子树,此时右子树上界大于当前最优价值,所以可能找到更优解.
    {
        cout<<"进入右子树深入一层,将到达第"<<i+1<<"层"<<endl;
        Backtrack(i+1); 
        cout<<"从右子树回溯一层,将到达第"<<i<<"层"<<endl;
    }
    else cout<<"尝试向右,计算得到Bound[i+1]:"<<Bound(i+1)<<"  Bound(i+1)<=bestp,不满足限界条件,直接剪枝"<<endl;
}
int Knap::Bound(int i)  //计算上界
{
    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;
}
class Object
{
    friend int Knapsack(int *, int *, int, int);
    public:
        // int operator<=(Object a) const {return d >= a.d;}  
        int ID;         //编号,保证排序后还能找到原来自己的重量和价值,从而用来构造一个新的重量数组以及价值数组
        float d;        //单位重量价值
};
bool cmp(Object a, Object b)
{
    return a.d >= b.d;
}

//template<class int, class int>
int Knapsack(int *p, int *w, int c, int n)      //为Knap::Backtrack初始化
{
    int W = 0;
    int P = 0;
    Object *Q = new Object[n+1];
    for(int i=1; i<=n; i++)
    {
        Q[i-1].ID = i;
        Q[i-1].d = 1.0*p[i]/w[i];
        P += p[i];
        W += w[i];
    }
    if(W <= c)  //能装入所有物品,直接返回P
        return P;
    sort(Q, Q+n, cmp);   //依物品单位重量价值排序
    // Sort(Q, n);
    int *temp_Number = new int[n+1];
    cout<<"排序后的数组为:";
    for(int i=1; i<=n; i++) 
    {
        temp_Number[i] = Q[i-1].ID;
        cout<<Q[i-1].ID<<" ";
    }
    cout<<endl;
    Knap K;   //利用处理好的Object对象来构建背包对象
    K.number = new int[n+1];
    K.number = temp_Number;
    K.select = new bool[n+1];
    for(int i=0; i<=n; i++) K.select[i] = false;    
    K.p = new int[n+1];
    K.w = new int[n+1];
    for(int i=1; i<=n; i++)  //构建一个排序之后的重量数组以及价值数组
    {
        K.p[i] = p[Q[i-1].ID];
        K.w[i] = w[Q[i-1].ID];
    }
    K.cp = 0;
    K.cw = 0;
    K.c = c;
    K.n = n;
    K.bestp = 0;
    K.Backtrack(1);
    delete[] Q;
    delete[] K.w;
    delete[] K.p;
    return K.bestp;
}
int main()
{
    cout<<"请输入背包总容量:";
    int c;
    while(cin>>c && c)
    {
        cout<<"请输入物品总件数:";
        int n;
        cin>>n;
        cout<<"请输入每件物品的重量以及价值"<<endl;
        int *w = new int[n+1];
        int *p = new int[n+1];
        for(int i=1; i<=n; i++)
        {
            cout<<"物品"<<i<<":";
            cin>>w[i]>>p[i];
        }
        int ans = Knapsack(p, w, c, n);
        cout<<"最优装载价值为:"<<ans<<endl;
        delete[] w;
        delete[] p;
        cout<<"请输入背包总容量:";
    }
    system("pause");
    return 0;
}