sebastianlay/der-gierige-backpacker

A greedy approximation for the bounded knapsack problem

Der gierige Backpacker

This is a C# implementation of a greedy approximation for the knapsack problem as part of the get int {IT} coding challenge.

Installation

Windows

• Download and install the .NET Core 3.1 Runtime
• Download the Windows version of the application from the releases and extract the content

Linux

• Download and install the .NET Core 3.1 Runtime
• Download the Linux version of the application from the releases and extract the content

Usage

• Open a console or PowerShell and navigate to the folder with the extracted application
• Run the application with the following optional arguments:

der-gierige-backpacker:
  A program to solve the bounded knapsack problem

Usage:
  der-gierige-backpacker [options]

Options:
  --filepath <filepath>    Path to the CSV file containing the items [default: code_for_bwi.csv]
  --trucks <trucks>        Comma-separated list of maximum truck capacities (in g) [default: 1027600,1014300]
  --version                Show version information
  -?, -h, --help           Show help and usage information

Credits

This application uses the following libraries:

• CsvHelper for reading and mapping the content of a CSV file
• System.CommandLine.DragonFruit for parsing the command line arguments

Solution

This greedy approximation for the bounded knapsack problem is way faster than brute forcing all possible combinations. However it does not guarantee to get the optimal solution. The solution for this particular CSV file can be found in a separate file.