干货 | 变邻域搜索算法解决0-1背包问题(Knapsack Problem)代码实例

用户1621951

发布于 2019-10-18 01:36:12

2.1K0

文章被收录于专栏：数据魔术师数据魔术师

前排吹水

经过小编这几天冒着挂科的风险，日日修炼，终于赶在考试周中又给大家更新了一篇干货文章。关于用变邻域搜索解决0-1背包问题的代码。怎样，大家有没有很感动？

什么是0-1背包问题？

0-1 背包问题：给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 w_i，其价值为 v_i 。问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？

为什么叫0-1背包问题呢？显然，面对每个物品，我们只有选择拿取或者不拿两种选择，不能选择装入某物品的一部分，也不能装入同一物品多次。拿就是1，不拿就是0。因此，就叫0-1背包问题。So simple, so naive.

代码小讲解

下面就几个邻域小动作给大家讲解一下。

解决方案设计

假设我们面前有n种物品，那么我们可以将解决方案设置成一个一维数组selection[n]。数组weights[n]表示重量，数组values[n]表示价值。

selection[i] = 1 表示装入第i个物品。
selection[i] = 0 表示不装入第i个物品。
总价值total_value = selection[i] * values[i]。 (i=1,2,3,4……n)
总重量total_weight = selection[i] * weights[i]。(i=1,2,3,4……n)

邻域动作1

将解决方案selection[n]的第i位取反(i=1,2,3,4……n)。比如：

有方案0010，那么生成的邻居解则有1010(第一位取反)、0110(第二位取反)、0000(第三位取反)、0011(第四位取反)。

不知道这么通俗易懂的大家understand了没有。

邻域动作2

对于解决方案selection[n]，在第i (i=1,2,3,4……n)位取反的情况下，依次将第j (j=i+1,2,3,4……n)位也取反。还是for 一个 example吧。

对于解决方案0010。产生的邻居解如下：

邻域动作3

交换第i位和第i-3位的数。如果i<3。就交换最后的，比如：

selection[0]和selection[n-1]交换。
selection[1]和selection[n-2]交换。
selection[2]和selection[n-3]交换。

shaking程序

这个比较简单，随机取反一些位就行了。

背包问题的代码

  1#include <iostream>
  2#include <vector>
  3#include <ctime>
  4#include <iomanip>
  5using namespace std;
  6
  7// 物品的数量 每一个物品有0和1两种选择 0代表选择当前物品 1代表不选择当前物品
  8const int n = 100;
  9
 10//算法最大迭代次数
 11const int Max_Iteration = 1000;
 12
 13//邻域数量
 14const int MaxFlip = 3;
 15int flip = 1;
 16
 17
 18//背包最大容量
 19const int maxWeight = 5 * n;
 20
 21//记录已经检查的背包数量
 22int solutionsChecked = 0;
 23
 24//物品对应价值&&重量
 25int values[n] = { 0 };
 26int weights[n] = { 0 };
 27
 28//随机数种子
 29const int seed = 5113; //2971
 30
 31
 32typedef struct Knapsack_Problem_Solution
 33{
 34    int selection[n] = { 0 };  //当前方案的物品选择情况 selection[i] == 0 or 1 <==> 不选择 or 选择 第i个物品
 35    int total_values = 0;      //当前方案下物品总价值
 36    int total_weights = 0;    //当前方案下物品总重量
 37}KP_Solution;
 38
 39//对selection[n]进行评价，计算total_values和total_weights
 40void Evaluate_Solution(KP_Solution & x)
 41{
 42    x.total_values = 0;
 43    x.total_weights = 0;
 44    for (int i = 0; i < n; i++)
 45    {
 46        x.total_values += x.selection[i] * values[i];
 47        x.total_weights += x.selection[i] * weights[i];
 48    }
 49
 50    if (x.total_weights > maxWeight)
 51    {
 52        x.total_values = maxWeight - x.total_weights; //超过背包最大容纳重量，价值设置为负数
 53    }
 54
 55}
 56
 57
 58//邻居解集合
 59vector<KP_Solution> nbrhood;
 60
 61void MySwap(int &a, int &b)
 62{
 63    int temp = a;
 64    a = b;
 65    b = temp;
 66}
 67
 68//利用邻域动作生成邻居解
 69void neighborhood(KP_Solution &x, int flip)
 70{
 71    //邻域动作1
 72    if (flip == 1)
 73    {
 74        nbrhood.clear();
 75        for (int i = 0; i < n; i++)
 76        {
 77            nbrhood.push_back(x);
 78            if (nbrhood[i].selection[i] == 1)
 79            {
 80                nbrhood[i].selection[i] = 0;
 81            }
 82            else
 83            {
 84                nbrhood[i].selection[i] = 1;
 85            }
 86        }
 87    }
 88    //邻域动作2
 89    else if (flip == 2)
 90    {
 91        nbrhood.clear();
 92        int a = -1;
 93        for (int i = 0; i < n; i++)
 94        {
 95            for (int j = i; j < n; j++)
 96            {
 97                if (i != j)
 98                {
 99                    a += 1;
100                    nbrhood.push_back(x);
101
102                    if (nbrhood[a].selection[i] == 1)
103                    {
104                        nbrhood[a].selection[i] = 0;
105                    }
106                    else
107                    {
108                        nbrhood[a].selection[i] = 1;
109                    }
110
111                    if (nbrhood[a].selection[j] == 1)
112                    {
113                        nbrhood[a].selection[j] = 0;
114                    }
115                    else
116                    {
117                        nbrhood[a].selection[j] = 1;
118                    }
119
120                }
121            }
122        }
123    }
124    //邻域动作3
125    else
126    {
127        nbrhood.clear();
128        for (int i = 0; i < n; i++)
129        {
130            nbrhood.push_back(x);
131            if ( i < 3)
132            {
133                MySwap(nbrhood[i].selection[i], nbrhood[i].selection[n + i - 3]);
134            }
135            else
136            {
137                MySwap(nbrhood[i].selection[i], nbrhood[i].selection[i - 3]);
138            }
139        }
140    }
141
142
143}
144//随机生成价值和重量
145void Rand_Value_Weight()
146{
147    
148    for (int i = 0; i < n; i++)
149    {
150        values[i] = rand() % 90 + 10; // 10 - 100
151        weights[i] = rand() % 15 + 5; // 5 - 20
152    }
153}
154
155//随机生成解决方案
156void Random_Solution(KP_Solution &x)
157{
158    x.total_values = 0;
159    x.total_weights = 0;
160
161    for (int i = 0; i < n; i++)
162    {
163        double rate = (rand() % 100) / 100.0;
164        if ( rate < 0.8 )
165        {
166            x.selection[i] = 0;
167        }
168        else
169        {
170            x.selection[i] = 1;
171        }
172    }
173}
174
175void Variable_Neighborhood_Descent(KP_Solution &x)
176{
177    int flip = 1;
178    KP_Solution x_curr;
179    while ( flip < MaxFlip + 1)
180    {
181        neighborhood(x, flip);
182        x_curr = nbrhood[0];
183        Evaluate_Solution(x_curr);
184
185        for(unsigned int i = 1; i < nbrhood.size(); i++)
186        {
187            solutionsChecked += 1;
188
189            Evaluate_Solution(nbrhood[i]);
190
191            if (nbrhood[i].total_values > x_curr.total_values)
192            {
193                x_curr = nbrhood[i];
194            }
195        }
196        //邻域复位
197        if (x_curr.total_weights > x.total_weights)
198        {
199            x = x_curr;
200            flip = 1;
201        }
202        else
203        {
204            flip += 1;
205        }
206    }
207}
208
209
210
211
212void Shaking_Procdure(KP_Solution &x)
213{
214    
215
216    int num = rand() % (n / 10) + 3; // 3 - 8
217    for (int i = 0; i < num; i++)
218    {
219        int pos = rand() % n;
220        if (x.selection[i] == 0)
221        {
222            x.selection[i] = 1;
223        }
224        else
225        {
226            x.selection[i] = 0;
227        }
228    }
229
230    Evaluate_Solution(x);
231}
232
233void Variable_Neighborhood_Search(KP_Solution &x, int iteration)
234{
235    KP_Solution best = x;
236    Variable_Neighborhood_Descent(best);
237    for (int i = 0; i < iteration; i++)
238    {
239        Shaking_Procdure(x);
240
241        Variable_Neighborhood_Descent(x);
242        if (best.total_values < x.total_values)
243        {
244            best = x;
245        }
246    }
247
248    x = best;
249}
250
251int main()
252{
253    KP_Solution kpx;
254      srand(seed);
255    Rand_Value_Weight();
256
257    Random_Solution(kpx);
258
259    Variable_Neighborhood_Search(kpx, Max_Iteration);
260
261    cout << "石头重量为：" << endl;
262
263    for (int i = 0; i < n; i++)
264    {
265        cout << setw(2) <<weights[i] << "  ";
266        if ((i + 1) % 25 == 0)
267        {
268            cout << endl;
269        }
270    }
271
272    cout << "\n石头价值为：" << endl;
273
274    for (int i = 0; i < n; i++)
275    {
276        cout << values[i] << "  ";
277        if ((i + 1) % 25 == 0)
278        {
279            cout << endl;
280        }
281    }
282
283    cout << endl << "最终结果: 已检查的总方案数 = " << solutionsChecked << endl;
284    cout << "背包最大容量为:" << maxWeight << endl;
285    cout << "找到最大价值为: " << kpx.total_values << endl;
286    cout << "背包当前重量为: " << kpx.total_weights << endl;
287
288    for (int i = 0; i < n; i++)
289    {
290        cout << kpx.selection[i] << "  ";
291        if ((i+1) % 25 == 0)
292        {
293            cout << endl;
294        }
295    }
296
297    return 0;
298}

运行结果：