Coders Packet

Knapsack for large number of elements and capacity in C++

By Abhishek Malviya

Knapsack for a large number of elements and for a huge capacity using a file system in C++.

A C++ program to work with significant size Knapsack problems. Ideally with 5000 elements and a capacity of 1000000.

This program uses a C++ file system to deal with large-sized Knapsacks as running it on a decent-sized ram is impossible due to memory limitation, so using a hard drive to save a state.

Provided functions.

Knapsack( vector weights, vector prices, int capacity);
void calculate();
void rePopulate(std::vector weights, std::vector prices, int capacity)


Constructor function takes three arguments weights, prices, and capacity.
In which weight is the weight of an element, or it can be called a penalty for an element which is paid from the capacity.
Capacity is the total weight that a Knapsack can carry or the penalty that we can pay to carry a particular element.
Price is the value that we will get for a particular element. This program aims to maximize the price that we can get.

The constructor function will act as an input point for our class, and all three properties need to be provided at the initialization point. If a user wants to reuse the same instance, then rePopulate function can reinitialize the instance.

The calculate function returns a vector with elements chosen for a particular value of weights, prices, and capacity.

How to use it?

void example()
  std::vector values = {2, 3, 5, 4};
  std::vector weights = {4, 5, 1, 5};
  int cap = 10;

  KnapsackFile ksf(values, weights, cap);

  std::vector ans = ksf.calculate();

  for (auto i : ans)
    std::cout << i << " " << std::endl;



Download Complete Code


No comments yet