剪枝函数-----0-1背包问题(c++)_01背包问题剪枝函数

#include <iostream>
using namespace std;

        #define N 100  //默认有99个物品。第一个不使用
        int w[N];  //每个物品的重量
        int v[N];  //每个物品的价值
        int n,c;    //n：一共有多少物品，c：背包的最大容量

        int cw = 0; //当前放入背包的物品总重量,随着对解空间的不断深入而变化
        int cv = 0;  //当前放入背包的物品总价值,随着对解空间的不断深入而变化
        int bestv = 0; //最优值；当前的最大价值，初始化为0，满足的话就连同修改储存的最优解 
        
        int x[N];   //x[i]=1：物品i放入背包，0代表不放入
        int bestx[N]; //最优解；bestx[i]=1代表物品i放入背包，0代表不放入

void input()
        {
        cout<<"How many items ?  ";
        cin>>n;
        cout<<endl;
        cout<<"How much capacity ?  ";
        cin>>c;
        cout<<endl;
        cout<<"The weight of items :  ";
        for(int i = 1; i <= n; i++)
        {
        cin>>w[i];
        }
        cout<<endl;
        cout<<"The value of items :  ";
        for(int i = 1; i <= n; i++)
        {
        cin>>v[i];
        }
        cout<<endl;
        }

void output()
        {
        cout<<"Maximun capacity:  "<<bestv<<endl;
        cout<<endl;
        cout<<"Optimal solution:  ( ";
        for(int i=1;i<=n;i++)
        cout<<bestx[i]<<" ";
        cout<<")"<<endl;
        }

int Bound(int i){//以物品单位重量价值递减顺序装入物品
        int cleft=c-cw;//背包剩余容量 
        int b = cv;//当前已放入的价值 
        while(i<=n && w[i]<=cleft){//i<=n不越界,w[i]<cleft 表明剩余容量还够，能放 
        cleft=cleft-w[i];
        b=b+v[i];
        i++;
        }
        if(i<=n)//与上面的while 相比，没有了w[i]<=cleft，还有i<=n，表明没有到达子树，但有cleft的，再挤挤东西进去 
        b=b+v[i]*cleft/w[i];
        return b;
        }

void backtrack(int t) //回溯函数 参数t表示当前处在第几层做抉择，t=1时表示当前在决定是否将第一个物品放入背包
        {
        if(t>n) //叶子节点，输出结果
        {
        if(cv>bestv)//如果找到了一个更优的解,保存更优的值和解
        {
        bestv = cv;
        for(int i=1; i<=n; ++i)
        bestx[i] = x[i];
        }
        }
        else
        {
        for(int i=0; i<=1; ++i) //遍历当前节点的子节点：0 不放入背包，1放入背包
        {
        x[t]=i;

        if(i==0&&Bound(t+1)>bestv) //左子树，不放入背包i==0，限界函数为Bound有没有潜在可能的比bestv更好的最优值，都满足则进入
        {
        backtrack(t+1);
        }
        else
        {
        if(i==1&&(cw+w[t])<=c)//右子树，放入背包i==1，约束函数为放入的物品重量总和不大于背包最大容量，都满足则进入
        {
        cw += w[t];
        cv += v[t];
        backtrack(t+1);
        cw -= w[t];
        cv -= v[t];
        }
        }
        }
        }
        }

int main()
        {
        input();
        backtrack(1);
        output();
        return 0;
        }
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