回溯法解决0-1背包问题（递归）_利用回溯法的递归框架,实现 01 背包问题,(问题设定:背包的限定重 量为 6,物品数量

#include<bits/stdc++.h>
using namespace std;
class Knap{
    friend int Knapsack(int*,int*,int,int,Knap&);
public:
   int c;      //背包容量
    int n;      //物品个数
    int* w;     //重量信息
    int* p;     //价值信息
    int cw;     //当前重量
    int cp;     //当前价值
    int bestp;  //当前最优价值
    int *x,     //当前解
        *bestx; //当前最优解
    int Bound(int i);            //限界函数
    void Backtrack(int i);       //递归深度优先遍历
};
int Knap::Bound(int i){
    int cleft = c - cw;  
    int b = cp;
    while(i<=n&&w[i]<=cleft){
        b += p[i];
        cleft -= w[i];
        i++;
    }
    if(i<=n) b += cleft*(p[i]/w[i]);
    return b;
}
void Knap::Backtrack(int i){
    if(i>n){
        bestp = cp;
        for(int i=1;i<=n;i++){
            bestx[i] = x[i];
        }
        for(int i=1;i<=n;i++){
            cout<<bestx[i]<<" "; 
        }
        cout<<" value "<<cp<<endl;
        return;
    }
    else{
        if(cw + w[i]<=c){//cw+w[i]  代表第i层左子树的重量
            x[i] = 1;
            cw += w[i];
            cp += p[i]; 
            Backtrack(i+1);//继续深度优先搜索
            cw -= w[i];    //回溯时要更新相应值
            cp -= p[i];
        }
        if(Bound(i+1) > bestp)//Bound(i+1)代表第i层右子树的限界函数
        {
            x[i] = 0;
            Backtrack(i+1);  //继续深度优先搜索
        }

    }
}
class Object{               //物品类
    friend int Knapsack(int*,int*,int,int,Knap&);
    friend bool cmp(Object,Object);
private:
    int id;
    double aver;
};
bool cmp(Object a,Object b){
    return a.aver>b.aver;
}
int Knapsack(int* w,int* p,int c,int n,Knap& K){
    int W = 0;
    int P = 0;
    Object* Q = new Object[n];
    for(int i=1;i<=n;i++){
        Q[i-1].id = i;
        Q[i-1].aver = 1.0*p[i]/w[i];
        P += p[i];
        W += w[i];
}
    if(W<c) return P;
    sort(Q,Q+n,cmp);     //按单位重量的价值排序
    K.p = new int[n+1];
    K.w = new int[n+1];
    K.x = new int[n+1];
    K.bestx = 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;delete [] K.x;
             return K.bestp;

}
void Init(int* &w,int* &p,int& c,int& n){
    cout<<"input number of object and capacity of bag"<<endl;
    cin>>n>>c;
    w = new int[n+1];
    p = new int[n+1];
    cout<<"input weight of objects"<<endl;
    for(int i=1;i<=n;i++){
        cin>>w[i];
    }
    cout<<"input value of objects"<<endl;
    for(int i=1;i<=n;i++){
        cin>>p[i];
    }
}
void Print(int bestp,int n,int*& x){
    cout<<"max value is"<<endl;
    cout<<bestp;
    cout<<"The optimal solution is"<<endl;
    for(int i=1;i<=n;i++){
        cout<<x[i]<<" ";
        }
}
int main(){
    int *w=NULL,*p=NULL;
    int c,n;
    Knap K;
    Init(w,p,c,n);
    Print(Knapsack(w,p,c,n,K),n,K.bestx);
    return 0;
}
//7 150
//35 30 60 50 40 10 25
//10 40 30 50 35 40 30
//170

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129