knapsack problem

annolliwohe (41)
Hello I found this code on a website (https://tfetimes.com/bounded-knapsack-problem/) is it possible to transform the weight limit and the weight of each object into comma numbers rather than whole numbers? Thank you

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
223
224
225
 
#include <iostream>

#include <vector>

#include <algorithm>

#include <stdexcept>

#include <memory>

#include <sys/time.h>

using std::cout;
using std::endl;

class StopTimer {
  public:
    StopTimer(): begin_(getUsec()) {}
  unsigned long long getTime() const {
    return getUsec() - begin_;
  }
  private:
    static unsigned long long getUsec() { //...you might want to use something else under Windows
      timeval tv;
      const int res = ::gettimeofday( & tv, 0);
      if (res)
        return 0;
      return tv.tv_usec + 1000000 * tv.tv_sec;
    }
  unsigned long long begin_;
};

struct KnapsackTask {
  struct Item {
    std::string name;
    unsigned w, v, qty;
    Item(): w(), v(), qty() {}
    Item(const std::string & iname, unsigned iw, unsigned iv, unsigned iqty):
      name(iname), w(iw), v(iv), qty(iqty) {}
  };
  typedef std::vector < Item > Items;
  struct Solution {
    unsigned v, w;
    unsigned long long iterations, usec;
    std::vector < unsigned > n;
    Solution(): v(), w(), iterations(), usec() {}
  };
  //...
  KnapsackTask(): maxWeight_(), totalWeight_() {}
  void add(const Item & item) {
    const unsigned totalItemWeight = item.w * item.qty;
    if (const bool invalidItem = !totalItemWeight)
      throw std::logic_error("Invalid item: " + item.name);
    totalWeight_ += totalItemWeight;
    items_.push_back(item);
  }
  const Items & getItems() const {
    return items_;
  }
  void setMaxWeight(unsigned maxWeight) {
    maxWeight_ = maxWeight;
  }
  unsigned getMaxWeight() const {
    return std::min(totalWeight_, maxWeight_);
  }

  private:
    unsigned maxWeight_, totalWeight_;
  Items items_;
};

class BoundedKnapsackRecursiveSolver {
  public:
    typedef KnapsackTask Task;
  typedef Task::Item Item;
  typedef Task::Items Items;
  typedef Task::Solution Solution;

  void solve(const Task & task) {
    Impl(task, solution_).solve();
  }
  const Solution & getSolution() const {
    return solution_;
  }
  private:
    class Impl {
      struct Candidate {
        unsigned v, n;
        bool visited;
        Candidate(): v(), n(), visited(false) {}
      };
      typedef std::vector < Candidate > Cache;
      public:
        Impl(const Task & task, Solution & solution):
        items_(task.getItems()),
        maxWeight_(task.getMaxWeight()),
        maxColumnIndex_(task.getItems().size() - 1),
        solution_(solution),
        cache_(task.getMaxWeight() * task.getItems().size()),
        iterations_(0) {}
      void solve() {
        if (const bool nothingToSolve = !maxWeight_ || items_.empty())
          return;
        StopTimer timer;
        Candidate candidate;
        solve(candidate, maxWeight_, items_.size() - 1);
        convertToSolution(candidate);
        solution_.usec = timer.getTime();
      }
      private:
        void solve(Candidate & current, unsigned reminderWeight,
          const unsigned itemIndex) {
          ++iterations_;

          const Item & item(items_[itemIndex]);

          if (const bool firstColumn = !itemIndex) {
            const unsigned maxQty = std::min(item.qty, reminderWeight / item.w);
            current.v = item.v * maxQty;
            current.n = maxQty;
            current.visited = true;
          } else {
            const unsigned nextItemIndex = itemIndex - 1; {
              Candidate & nextItem = cachedItem(reminderWeight, nextItemIndex);
              if (!nextItem.visited)
                solve(nextItem, reminderWeight, nextItemIndex);
              current.visited = true;
              current.v = nextItem.v;
              current.n = 0;
            }
            if (reminderWeight >= item.w) {
              for (unsigned numberOfItems = 1; numberOfItems <= item.qty; ++numberOfItems) {
                reminderWeight -= item.w;
                Candidate & nextItem = cachedItem(reminderWeight, nextItemIndex);
                if (!nextItem.visited)
                  solve(nextItem, reminderWeight, nextItemIndex);

                const unsigned checkValue = nextItem.v + numberOfItems * item.v;
                if (checkValue > current.v) {
                  current.v = checkValue;
                  current.n = numberOfItems;
                }
                if (!(reminderWeight >= item.w))
                  break;
              }
            }
          }
        }
      void convertToSolution(const Candidate & candidate) {
        solution_.iterations = iterations_;
        solution_.v = candidate.v;
        solution_.n.resize(items_.size());

        const Candidate * iter = & candidate;
        unsigned weight = maxWeight_, itemIndex = items_.size() - 1;
        while (true) {
          const unsigned currentWeight = iter -> n * items_[itemIndex].w;
          solution_.n[itemIndex] = iter -> n;
          weight -= currentWeight;
          if (!itemIndex--)
            break;
          iter = & cachedItem(weight, itemIndex);
        }
        solution_.w = maxWeight_ - weight;
      }
      Candidate & cachedItem(unsigned weight, unsigned itemIndex) {
        return cache_[weight * maxColumnIndex_ + itemIndex];
      }
      const Items & items_;
      const unsigned maxWeight_;
      const unsigned maxColumnIndex_;
      Solution & solution_;
      Cache cache_;
      unsigned long long iterations_;
    };
  Solution solution_;
};

void populateDataset(KnapsackTask & task) {
  typedef KnapsackTask::Item Item;
  task.setMaxWeight(400);
  task.add(Item("map", 9, 150, 1));
  task.add(Item("compass", 13, 35, 1));
  task.add(Item("water", 153, 200, 2));
  task.add(Item("sandwich", 50, 60, 2));
  task.add(Item("glucose", 15, 60, 2));
  task.add(Item("tin", 68, 45, 3));
  task.add(Item("banana", 27, 60, 3));
  task.add(Item("apple", 39, 40, 3));
  task.add(Item("cheese", 23, 30, 1));
  task.add(Item("beer", 52, 10, 3));
  task.add(Item("suntancream", 11, 70, 1));
  task.add(Item("camera", 32, 30, 1));
  task.add(Item("T-shirt", 24, 15, 2));
  task.add(Item("trousers", 48, 10, 2));
  task.add(Item("umbrella", 73, 40, 1));
  task.add(Item("w-trousers", 42, 70, 1));
  task.add(Item("w-overclothes", 43, 75, 1));
  task.add(Item("note-case", 22, 80, 1));
  task.add(Item("sunglasses", 7, 20, 1));
  task.add(Item("towel", 18, 12, 2));
  task.add(Item("socks", 4, 50, 1));
  task.add(Item("book", 30, 10, 2));
}

int main() {
  KnapsackTask task;
  populateDataset(task);

  BoundedKnapsackRecursiveSolver solver;
  solver.solve(task);
  const KnapsackTask::Solution & solution = solver.getSolution();

  cout << "Iterations to solve: " << solution.iterations << endl;
  cout << "Time to solve: " << solution.usec << " usec" << endl;
  cout << "Solution:" << endl;
  for (unsigned i = 0; i < solution.n.size(); ++i) {
    if (const bool itemIsNotInKnapsack = !solution.n[i])
      continue;
    cout << "  " << solution.n[i] << ' ' << task.getItems()[i].name << " ( item weight = " << task.getItems()[i].w << " )" << endl;
  }

  cout << "Weight: " << solution.w << " Value: " << solution.v << endl;
  return 0;
}
Last edited on
jonnin (11437)
do you mean 3.14159 or 3,14159 (, and . change depending on country)?
if so,
double type is what you want:
eg line 68 replace unsigned with double, but you will have to fix it everywhere that applies to weight.
annolliwohe (41)
Like this ?

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
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>
#include <memory>
#include <sys/time.h>
 
using std::cout;
using std::endl;
 
class StopTimer
{
public:
    StopTimer(): begin_(getUsec()) {}
    unsigned long long getTime() const { return getUsec() - begin_; }
private:
    static unsigned long long getUsec()
    {//...you might want to use something else under Windows
        timeval tv;
        const int res = ::gettimeofday(&tv, 0);
        if(res)
            return 0;
        return tv.tv_usec + 1000000 * tv.tv_sec;
    }
    unsigned long long begin_;
};
 
struct KnapsackTask
{
    struct Item
    {
        std::string name;
        unsigned v;
        double w, qty;
        Item(): w(), v(), qty() {}
        Item(const std::string& iname, double iw, unsigned iv, double iqty):
            name(iname), w(iw), v(iv), qty(iqty)
        {}
    };
    typedef std::vector<Item> Items;
    struct Solution
    {
        unsigned v, w;
        unsigned long long iterations, usec;
        std::vector<unsigned> n;
        Solution(): v(), w(), iterations(), usec() {}
    };
    //...
    KnapsackTask(): maxWeight_(), totalWeight_() {}
    void add(const Item& item)
    {
        double totalItemWeight = item.w * item.qty;
        if(const bool invalidItem = !totalItemWeight)
            throw std::logic_error("Invalid item: " + item.name);
        totalWeight_ += totalItemWeight;
        items_.push_back(item);
    }
    const Items& getItems() const { return items_; }
    void setMaxWeight(double maxWeight) { maxWeight_ = maxWeight; }
    double getMaxWeight() const { return std::min(totalWeight_, maxWeight_); }
 
private:
    double maxWeight_, totalWeight_;
    Items items_;
};
 
class BoundedKnapsackRecursiveSolver
{
public:
    typedef KnapsackTask Task;
    typedef Task::Item Item;
    typedef Task::Items Items;
    typedef Task::Solution Solution;
 
    void solve(const Task& task)
    {
        Impl(task, solution_).solve();
    }
    const Solution& getSolution() const { return solution_; }
private:
    class Impl
    {
        struct Candidate
        {
            unsigned v, n;
            bool visited;
            Candidate(): v(), n(), visited(false) {}
        };
        typedef std::vector<Candidate> Cache;
    public:
        Impl(const Task& task, Solution& solution):
            items_(task.getItems()),
            maxWeight_(task.getMaxWeight()),
            maxColumnIndex_(task.getItems().size() - 1),
            solution_(solution),
            cache_(task.getMaxWeight() * task.getItems().size()),
            iterations_(0)
        {}
        void solve()
        {
            if(const bool nothingToSolve = !maxWeight_ || items_.empty())
                return;
            StopTimer timer;
            Candidate candidate;
            solve(candidate, maxWeight_, items_.size() - 1);
            convertToSolution(candidate);
            solution_.usec = timer.getTime();
        }
    private:
        void solve(Candidate& current, double reminderWeight, const unsigned itemIndex)
        {
            ++iterations_;
 
            const Item& item(items_[itemIndex]);
 
            if(const bool firstColumn = !itemIndex)
            {
                double maxQty = std::min(item.qty, reminderWeight/item.w);
                current.v = item.v * maxQty;
                current.n = maxQty;
                current.visited = true;
            }
            else
            {
                const unsigned nextItemIndex = itemIndex - 1;
                {
                    Candidate& nextItem = cachedItem(reminderWeight, nextItemIndex);
                    if(!nextItem.visited)
                        solve(nextItem, reminderWeight, nextItemIndex);
                    current.visited = true;
                    current.v = nextItem.v;
                    current.n = 0;
                }
                if(reminderWeight >= item.w)
                {
                    for (unsigned numberOfItems = 1; numberOfItems <= item.qty; ++numberOfItems)
                    {
                        reminderWeight -= item.w;
                        Candidate& nextItem = cachedItem(reminderWeight, nextItemIndex);
                        if(!nextItem.visited)
                            solve(nextItem, reminderWeight, nextItemIndex);
 
                        const unsigned checkValue = nextItem.v + numberOfItems * item.v;
                        if ( checkValue > current.v)
                        {
                            current.v = checkValue;
                            current.n = numberOfItems;
                        }
                        if(!(reminderWeight >= item.w))
                            break;
                    }
                }
            }
        }
        void convertToSolution(const Candidate& candidate)
        {
            solution_.iterations = iterations_;
            solution_.v = candidate.v;
            solution_.n.resize(items_.size());
 
            const Candidate* iter = &candidate;
            unsigned weight = maxWeight_, itemIndex = items_.size() - 1;
            while(true)
            {
                const unsigned currentWeight = iter->n * items_[itemIndex].w;
                solution_.n[itemIndex] = iter->n;
                weight -= currentWeight;
                if(!itemIndex--)
                    break;
                iter = &cachedItem(weight, itemIndex);
            }
            solution_.w = maxWeight_ - weight;
        }
        Candidate& cachedItem(unsigned weight, unsigned itemIndex)
        {
            return cache_[weight * maxColumnIndex_ + itemIndex];
        }
        const Items& items_;
        const unsigned maxWeight_;
        const unsigned maxColumnIndex_;
        Solution& solution_;
        Cache cache_;
        unsigned long long iterations_;
    };
    Solution solution_;
};
 
void populateDataset(KnapsackTask& task)
{
    typedef KnapsackTask::Item Item;
    task.setMaxWeight( 400 );
    task.add(Item("map",9.20,150,1));
    task.add(Item("compass",13.10,35,1));
    task.add(Item("water",153.50,200,2));
    task.add(Item("sandwich",50,60,2));
    task.add(Item("glucose",15,60,2));
    task.add(Item("tin",68,45,3));
    task.add(Item("banana",27,60,3));
    task.add(Item("apple",39,40,3));
    task.add(Item("cheese",23,30,1));
    task.add(Item("beer",52,10,3));
    task.add(Item("suntancream",11,70,1));
    task.add(Item("camera",32,30,1));
    task.add(Item("T-shirt",24,15,2));
    task.add(Item("trousers",48,10,2));
    task.add(Item("umbrella",73,40,1));
    task.add(Item("w-trousers",42,70,1));
    task.add(Item("w-overclothes",43,75,1));
    task.add(Item("note-case",22,80,1));
    task.add(Item("sunglasses",7,20,1));
    task.add(Item("towel",18,12,2));
    task.add(Item("socks",4,50,1));
    task.add(Item("book",30,10,2));
}
 
int main()
{
    KnapsackTask task;
    populateDataset(task);
 
    BoundedKnapsackRecursiveSolver solver;
    solver.solve(task);
    const KnapsackTask::Solution& solution = solver.getSolution();
 
    cout << "Iterations to solve: " << solution.iterations << endl;
    cout << "Time to solve: " << solution.usec << " usec" << endl;
    cout << "Solution:" << endl;
    for (unsigned i = 0; i < solution.n.size(); ++i)
    {
        if (const bool itemIsNotInKnapsack = !solution.n[i])
            continue;
        cout << "  " << solution.n[i] << ' ' << task.getItems()[i].name << " ( item weight = " << task.getItems()[i].w << " )" << endl;
    }
 
    cout << "Weight: " << solution.w << " Value: " << solution.v << endl;
    return 0;
}
jonnin (11437)
@162, 165, 179 ... you need to go back over this.
Last edited on
annolliwohe (41)
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
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>
#include <memory>
#include <sys/time.h>
 
using std::cout;
using std::endl;
 
class StopTimer
{
public:
    StopTimer(): begin_(getUsec()) {}
    unsigned long long getTime() const { return getUsec() - begin_; }
private:
    static unsigned long long getUsec()
    {//...you might want to use something else under Windows
        timeval tv;
        const int res = ::gettimeofday(&tv, 0);
        if(res)
            return 0;
        return tv.tv_usec + 1000000 * tv.tv_sec;
    }
    unsigned long long begin_;
};
 
struct KnapsackTask
{
    struct Item
    {
        std::string name;
        unsigned v;
        double w, qty;
        Item(): w(), v(), qty() {}
        Item(const std::string& iname, double iw, unsigned iv, double iqty):
            name(iname), w(iw), v(iv), qty(iqty)
        {}
    };
    typedef std::vector<Item> Items;
    struct Solution
    {
        unsigned v, w;
        unsigned long long iterations, usec;
        std::vector<unsigned> n;
        Solution(): v(), w(), iterations(), usec() {}
    };
    //...
    KnapsackTask(): maxWeight_(), totalWeight_() {}
    void add(const Item& item)
    {
        double totalItemWeight = item.w * item.qty;
        if(const bool invalidItem = !totalItemWeight)
            throw std::logic_error("Invalid item: " + item.name);
        totalWeight_ += totalItemWeight;
        items_.push_back(item);
    }
    const Items& getItems() const { return items_; }
    void setMaxWeight(double maxWeight) { maxWeight_ = maxWeight; }
    double getMaxWeight() const { return std::min(totalWeight_, maxWeight_); }
 
private:
    double maxWeight_, totalWeight_;
    Items items_;
};
 
class BoundedKnapsackRecursiveSolver
{
public:
    typedef KnapsackTask Task;
    typedef Task::Item Item;
    typedef Task::Items Items;
    typedef Task::Solution Solution;
 
    void solve(const Task& task)
    {
        Impl(task, solution_).solve();
    }
    const Solution& getSolution() const { return solution_; }
private:
    class Impl
    {
        struct Candidate
        {
            unsigned v, n;
            bool visited;
            Candidate(): v(), n(), visited(false) {}
        };
        typedef std::vector<Candidate> Cache;
    public:
        Impl(const Task& task, Solution& solution):
            items_(task.getItems()),
            maxWeight_(task.getMaxWeight()),
            maxColumnIndex_(task.getItems().size() - 1),
            solution_(solution),
            cache_(task.getMaxWeight() * task.getItems().size()),
            iterations_(0)
        {}
        void solve()
        {
            if(const bool nothingToSolve = !maxWeight_ || items_.empty())
                return;
            StopTimer timer;
            Candidate candidate;
            solve(candidate, maxWeight_, items_.size() - 1);
            convertToSolution(candidate);
            solution_.usec = timer.getTime();
        }
    private:
        void solve(Candidate& current, double reminderWeight, const unsigned itemIndex)
        {
            ++iterations_;
 
            const Item& item(items_[itemIndex]);
 
            if(const bool firstColumn = !itemIndex)
            {
                double maxQty = std::min(item.qty, reminderWeight/item.w);
                current.v = item.v * maxQty;
                current.n = maxQty;
                current.visited = true;
            }
            else
            {
                const unsigned nextItemIndex = itemIndex - 1;
                {
                    Candidate& nextItem = cachedItem(reminderWeight, nextItemIndex);
                    if(!nextItem.visited)
                        solve(nextItem, reminderWeight, nextItemIndex);
                    current.visited = true;
                    current.v = nextItem.v;
                    current.n = 0;
                }
                if(reminderWeight >= item.w)
                {
                    for (unsigned numberOfItems = 1; numberOfItems <= item.qty; ++numberOfItems)
                    {
                        reminderWeight -= item.w;
                        Candidate& nextItem = cachedItem(reminderWeight, nextItemIndex);
                        if(!nextItem.visited)
                            solve(nextItem, reminderWeight, nextItemIndex);
 
                        const unsigned checkValue = nextItem.v + numberOfItems * item.v;
                        if ( checkValue > current.v)
                        {
                            current.v = checkValue;
                            current.n = numberOfItems;
                        }
                        if(!(reminderWeight >= item.w))
                            break;
                    }
                }
            }
        }
        void convertToSolution(const Candidate& candidate)
        {
            solution_.iterations = iterations_;
            solution_.v = candidate.v;
            solution_.n.resize(items_.size());
 
            const Candidate* iter = &candidate;
            double weight = maxWeight_, itemIndex = items_.size() - 1;
            while(true)
            {
                double currentWeight = iter->n * items_[itemIndex].w;
                solution_.n[itemIndex] = iter->n;
                weight -= currentWeight;
                if(!itemIndex--)
                    break;
                iter = &cachedItem(weight, itemIndex);
            }
            solution_.w = maxWeight_ - weight;
        }
        Candidate& cachedItem(unsigned weight, unsigned itemIndex)
        {
            return cache_[weight * maxColumnIndex_ + itemIndex];
        }
        const Items& items_;
        double maxWeight_;
        const unsigned maxColumnIndex_;
        Solution& solution_;
        Cache cache_;
        unsigned long long iterations_;
    };
    Solution solution_;
};
 
void populateDataset(KnapsackTask& task)
{
    typedef KnapsackTask::Item Item;
    task.setMaxWeight( 450.60 );
    task.add(Item("map",9.20,150,1));
    task.add(Item("compass",13.10,35,1));
    task.add(Item("water",153.50,200,2));
    task.add(Item("sandwich",50.2,60,2));
    task.add(Item("glucose",15.1,60,2));
    task.add(Item("tin",68.3,45,3));
    task.add(Item("banana",27.1,60,3));
    task.add(Item("apple",39.2,40,3));
    task.add(Item("cheese",23.1,30,1));
    task.add(Item("beer",52.5,10,3));
    task.add(Item("suntancream",11.3,70,1));
    task.add(Item("camera",32.1,30,1));
    task.add(Item("T-shirt",24.1,15,2));
    task.add(Item("trousers",48.2,10,2));
    task.add(Item("umbrella",73.3,40,1));
    task.add(Item("w-trousers",42.1,70,1));
    task.add(Item("w-overclothes",43.5,75,1));
    task.add(Item("note-case",22.2,80,1));
    task.add(Item("sunglasses",7.1,20,1));
    task.add(Item("towel",18.9,12,2));
    task.add(Item("socks",4.4,50,1));
    task.add(Item("book",30.2,10,2));
}
 
int main()
{
    KnapsackTask task;
    populateDataset(task);
 
    BoundedKnapsackRecursiveSolver solver;
    solver.solve(task);
    const KnapsackTask::Solution& solution = solver.getSolution();
 
    cout << "Iterations to solve: " << solution.iterations << endl;
    cout << "Time to solve: " << solution.usec << " usec" << endl;
    cout << "Solution:" << endl;
    for (unsigned i = 0; i < solution.n.size(); ++i)
    {
        if (const bool itemIsNotInKnapsack = !solution.n[i])
            continue;
        cout << "  " << solution.n[i] << ' ' << task.getItems()[i].name << " ( item weight = " << task.getItems()[i].w << " )" << endl;
    }
 
    cout << "Weight: " << solution.w << " Value: " << solution.v << endl;
    return 0;
}


It's good, like this ?
jonnin (11437)
43? 174?

Do you have grep? Or some other search tool? Just look through the code for the weight variables and where they are defined... those are the last 2 I see, but I just did it by hand.

this is very crude and rather old but if you don't have grep you can try it to search terms. It accepts multiple terms, eg whatever.exe filename.cpp w weight (see the problem with a variable name like w? its hard to isolate, you can put "w " or ".w " but wouldnt it be nice if it were called weight or mass or something distinct?)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
int main(int argc, char**argv)
{   
   ifstream ifs(argv[1]);
   char line[10000];
   bool in{};
   int ctr{};
   uint64_t i;
   while(ifs.getline(line,10000))   
   {	 
     ++ctr;
     in = false;
     for(i = 2; i < argc; i++)
	   in |= (bool)(strstr(line,argv[i]));
     if(in)
	 cout <<ctr<<"\t\t"<< line << endl;
   }
}

Last edited on
annolliwohe (41)
Hello, sorry I didn't have time to get back to it, like this is good?

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
 
#include <sys/time.h>

#include <algorithm>
#include <iostream>
#include <memory>
#include <stdexcept>
#include <vector>

using std::cout;
using std::endl;

class StopTimer {
 public:
  StopTimer() : begin_(getUsec()) {}
  unsigned long long getTime() const { return getUsec() - begin_; }

 private:
  static unsigned long long
  getUsec() {  //...you might want to use something else under Windows
    timeval tv;
    const int res = ::gettimeofday(&tv, 0);
    if (res) return 0;
    return tv.tv_usec + 1000000 * tv.tv_sec;
  }
  unsigned long long begin_;
};

struct KnapsackTask {
  struct Item {
    std::string name;
    unsigned v;
    double mass, qty;
    Item() : mass(), v(), qty() {}
    Item(const std::string& iname, double iw, unsigned iv, double iqty)
        : name(iname), mass(iw), v(iv), qty(iqty) {}
  };
  typedef std::vector<Item> Items;
  struct Solution {
    unsigned v;
    double mass;
    unsigned long long iterations, usec;
    std::vector<unsigned> n;
    Solution() : v(), mass(), iterations(), usec() {}
  };
  //...
  KnapsackTask() : maxWeight_(), totalWeight_() {}
  void add(const Item& item) {
    double totalItemWeight = item.mass * item.qty;
    if (const bool invalidItem = !totalItemWeight)
      throw std::logic_error("Invalid item: " + item.name);
    totalWeight_ += totalItemWeight;
    items_.push_back(item);
  }
  const Items& getItems() const { return items_; }
  void setMaxWeight(double maxWeight) { maxWeight_ = maxWeight; }
  double getMaxWeight() const { return std::min(totalWeight_, maxWeight_); }

 private:
  double maxWeight_, totalWeight_;
  Items items_;
};

class BoundedKnapsackRecursiveSolver {
 public:
  typedef KnapsackTask Task;
  typedef Task::Item Item;
  typedef Task::Items Items;
  typedef Task::Solution Solution;

  void solve(const Task& task) { Impl(task, solution_).solve(); }
  const Solution& getSolution() const { return solution_; }

 private:
  class Impl {
    struct Candidate {
      unsigned v, n;
      bool visited;
      Candidate() : v(), n(), visited(false) {}
    };
    typedef std::vector<Candidate> Cache;

   public:
    Impl(const Task& task, Solution& solution)
        : items_(task.getItems()),
          maxWeight_(task.getMaxWeight()),
          maxColumnIndex_(task.getItems().size() - 1),
          solution_(solution),
          cache_(task.getMaxWeight() * task.getItems().size()),
          iterations_(0) {}
    void solve() {
      if (const bool nothingToSolve = !maxWeight_ || items_.empty()) return;
      StopTimer timer;
      Candidate candidate;
      solve(candidate, maxWeight_, items_.size() - 1);
      convertToSolution(candidate);
      solution_.usec = timer.getTime();
    }

   private:
    void solve(Candidate& current, double reminderWeight,
               const unsigned itemIndex) {
      ++iterations_;

      const Item& item(items_[itemIndex]);

      if (const bool firstColumn = !itemIndex) {
        double maxQty = std::min(item.qty, reminderWeight / item.mass);
        current.v = item.v * maxQty;
        current.n = maxQty;
        current.visited = true;
      } else {
        const unsigned nextItemIndex = itemIndex - 1;
        {
          Candidate& nextItem = cachedItem(reminderWeight, nextItemIndex);
          if (!nextItem.visited) solve(nextItem, reminderWeight, nextItemIndex);
          current.visited = true;
          current.v = nextItem.v;
          current.n = 0;
        }
        if (reminderWeight >= item.mass) {
          for (unsigned numberOfItems = 1; numberOfItems <= item.qty;
               ++numberOfItems) {
            reminderWeight -= item.mass;
            Candidate& nextItem = cachedItem(reminderWeight, nextItemIndex);
            if (!nextItem.visited)
              solve(nextItem, reminderWeight, nextItemIndex);

            const unsigned checkValue = nextItem.v + numberOfItems * item.v;
            if (checkValue > current.v) {
              current.v = checkValue;
              current.n = numberOfItems;
            }
            if (!(reminderWeight >= item.mass)) break;
          }
        }
      }
    }
    void convertToSolution(const Candidate& candidate) {
      solution_.iterations = iterations_;
      solution_.v = candidate.v;
      solution_.n.resize(items_.size());

      const Candidate* iter = &candidate;
      double weight = maxWeight_, itemIndex = items_.size() - 1;
      while (true) {
        double currentWeight = iter->n * items_[itemIndex].mass;
        solution_.n[itemIndex] = iter->n;
        weight -= currentWeight;
        if (!itemIndex--) break;
        iter = &cachedItem(weight, itemIndex);
      }
      solution_.mass = maxWeight_ - weight;
    }
    Candidate& cachedItem(double weight, unsigned itemIndex) {
      return cache_[weight * maxColumnIndex_ + itemIndex];
    }
    const Items& items_;
    double maxWeight_;
    const unsigned maxColumnIndex_;
    Solution& solution_;
    Cache cache_;
    unsigned long long iterations_;
  };
  Solution solution_;
};

void populateDataset(KnapsackTask& task) {
  typedef KnapsackTask::Item Item;
  task.setMaxWeight(450.60);
  task.add(Item("map", 9.20, 150, 1));
  task.add(Item("compass", 13.10, 35, 1));
  task.add(Item("water", 153.50, 200, 2));
  task.add(Item("sandwich", 50.2, 60, 2));
  task.add(Item("glucose", 15.1, 60, 2));
  task.add(Item("tin", 68.3, 45, 3));
  task.add(Item("banana", 27.1, 60, 3));
  task.add(Item("apple", 39.2, 40, 3));
  task.add(Item("cheese", 23.1, 30, 1));
  task.add(Item("beer", 52.5, 10, 3));
  task.add(Item("suntancream", 11.3, 70, 1));
  task.add(Item("camera", 32.1, 30, 1));
  task.add(Item("T-shirt", 24.1, 15, 2));
  task.add(Item("trousers", 48.2, 10, 2));
  task.add(Item("umbrella", 73.3, 40, 1));
  task.add(Item("w-trousers", 42.1, 70, 1));
  task.add(Item("w-overclothes", 43.5, 75, 1));
  task.add(Item("note-case", 22.2, 80, 1));
  task.add(Item("sunglasses", 7.1, 20, 1));
  task.add(Item("towel", 18.9, 12, 2));
  task.add(Item("socks", 4.4, 50, 1));
  task.add(Item("book", 30.2, 10, 2));
}

int main() {
  KnapsackTask task;
  populateDataset(task);

  BoundedKnapsackRecursiveSolver solver;
  solver.solve(task);
  const KnapsackTask::Solution& solution = solver.getSolution();

  cout << "Iterations to solve: " << solution.iterations << endl;
  cout << "Time to solve: " << solution.usec << " usec" << endl;
  cout << "Solution:" << endl;
  for (unsigned i = 0; i < solution.n.size(); ++i) {
    if (const bool itemIsNotInKnapsack = !solution.n[i]) continue;
    cout << "  " << solution.n[i] << ' ' << task.getItems()[i].name
         << " ( item weight = " << task.getItems()[i].mass << " )" << endl;
  }

  cout << "Weight: " << solution.mass << " Value: " << solution.v << endl;
  return 0;
}
Topic archived. No new replies allowed.