当前位置:   article > 正文

分支界限法实现背包问题c++实现_分治界限法解决01背包问题c++

分治界限法解决01背包问题c++

在写代码的过程中参考了下面这篇博主的博客:背包问题
直接上代码,都有完整的注释的,喜欢就好:

//分支限界法
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
const int MAX_N = 22;
using namespace std;
int n; // 表示有n个物品
int weights=16;  //表示背包完整重量
int bound=0; //表示已有最优解
struct wu  //记录物品
{
    int i; //表示原来物品的索引
    int weight; //记录物品的重量
    int value; //记录物品的价值
    int sale ; //记录物品的价值/重量
};

struct Node
{
    wu w; //记录该节点选择的物品
    bool visited[MAX_N];//标记哪些点走了
    bool notvisited[MAX_N];//标记哪些点不选择走
    bool nochose[MAX_N]; //当前尚待选择的商品集合
    int k;   //已经选择的物品数
    int ub; //目标函数的值(目标结果)
    bool operator <(const Node &p)const
    {
        return p.ub > ub;//目标函数值小的先出队列
    }
};

priority_queue<Node> pq;//创建一个优先队列


void sort(wu *w) //冒泡排序
{
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(w[i].sale < w[j].sale)
            {
                wu temp = w[i];
                w[i] = w[j];
                w[j] = temp;
            }
        }
    }
}

//得到上界值
int get_ub(Node p,wu *w)
{
    int k = weights;
    int value=0;
    for(int i=0;i<n;i++)//背包剩余重量
    {
        if(p.visited[i] == true)
        {
            k-=w[i].weight;
            value+=w[i].value;
        }
    }
    //找到最大的价值比,排除已经被选择的
    cout<<"w:"<<weights-k<<"  v:"<<value<<endl;
    for(int i=0;i<n;i++)
    {
        if(p.nochose[i] == true) //找到的第一个就是最大价值比
        {
            cout<<"ub="<<value+k*w[i].sale<<endl;
            return value+k*w[i].sale;
        }
    }
    return value;
}

//判断nochose是否全为false即bound是否应该更新
bool isF(bool *nochose)
{
    for(int i=0;i<n;i++)
    {
        if(nochose[i]==true)
        {
            return false;
        }
    }
    return true;
}

int get_w(Node p,wu *w)
{
    int k =0;
    for(int i=0;i<n;i++)//背包剩余重量
    {
        if(p.visited[i] == true)
        {
            k+=w[i].weight;
        }
    }
    return k;
}
void slove(wu *w)
{
    //step2
    Node p;
    p.ub = 0;
    //step2 -2 初始化
    for(int i=0;i<n;i++) p.visited[i]=false;
    for(int i=0;i<n;i++) p.notvisited[i]=false;
    for(int i=0;i<n;i++) p.nochose[i]=true;
    p.k = 0;
    //step3
    while(p.k!=n)
    {
        //step4: 分支一,包含该节点
        Node Y;
        //判断包含该节点是否超重
        if(get_w(p,w)+w[p.k].weight<=weights)
        {   
            cout<<"包含物品:"<<w[p.k].i<<endl;
            for(int i=0;i<n;i++) Y.visited[i]=p.visited[i];
            Y.visited[p.k] = true;
            for(int i=0;i<n;i++) Y.notvisited[i]=p.notvisited[i];
            for(int i=0;i<n;i++) Y.nochose[i]=p.nochose[i];
            Y.nochose[p.k] = false;
            Y.k = p.k+1;
            //判断是否加入队列
            Y.ub =get_ub(Y,w);
            if(Y.ub > bound)
                pq.push(Y);
            //判断nochose是否全为false即bound是否应该更新
            if(isF(Y.nochose)==true)
            {
                cout<<"这是一个可行解:"<<Y.ub<<endl;
                if(bound<Y.ub)
                {
                    bound = Y.ub;
                }
                else{
                    cout<<"但是不如已有最优解好,减枝"<<endl;
                 }
            }
        }
        else
        {
            cout<<"包含物品"<<w[p.k].i<<"不可行"<<endl;
        }
        
        //step4(5): 分支二,不包含该节点
        Node Z;
        cout<<"不包含物品:"<<w[p.k].i<<endl;
        for(int i=0;i<n;i++) Z.visited[i]=p.visited[i];
        for(int i=0;i<n;i++) Z.notvisited[i]=p.notvisited[i];
        Z.notvisited[p.k] = true;
        for(int i=0;i<n;i++) Z.nochose[i]=p.nochose[i];
        Z.nochose[p.k] = false;
        Z.k = p.k+1;
        //判断是否加入队列
        Z.ub = get_ub(Z,w);
        if(Z.ub > bound)
            pq.push(Z);
        if(isF(Z.nochose)==true)
        {
            cout<<"这是一个可行解:"<<Z.ub<<endl;
            if(bound<Z.ub)
            {
                bound = Z.ub;
            }
            else{
                cout<<"但是不如已有最优解好,减枝"<<endl;
            }
        }
        p=pq.top();
        pq.pop();

    }   
    cout<<bound <<endl; //step3
    //输出选择的物品
    cout<<"选择的物品为"<<endl;
    for(int i=0;i<n;i++)
    {
        if(p.visited[i] == true)
        {
            cout<<w[i].i<<"\t";
        }
    }
}


int main()
{
    cout<<"请输入物品的数量:"<<endl;
    cin>>n; //输入物品的数量
    cout<<"请输入背包的承重量:"<<endl;
    cin>>weights;
    cout<<"请输入每一个物品的重量和价值:"<<endl;
    wu *w = new wu[n];
    for(int i=0;i<n;i++)
    {
        w[i].i = i;
        cin>>w[i].weight;
        cin>>w[i].value;
        w[i].sale = w[i].value/w[i].weight;
    }
    //step1
    bound = 0;
    sort(w);
    slove(w);
}
/*
实例
请输入物品的数量:
4
请输入背包的承重量:
10
请输入每一个物品的重量和价值:
4 40
7 42
5 25
3 12
*/
  • 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
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/501294
推荐阅读
相关标签
  

闽ICP备14008679号