OK_Projekt

Solver for multiple Knapsack Problem variants

Status

project in development

Done so far

• Brute Force Methods
• Primitive Branch and Bound Methods
• Greedy algorithms
• Dynamic Programming
• measure calculation time
• json format support

To Do

• Heuristics
• Multi threading
• GPU support

Problems

• Multi dimentional knapsack problem, but items are given as a graph, where each vertex in the graph is an item to pack. The problem is to find either path, cycle or tree in this graph, that fits in the knapsack and has maximum value.
• Knapsack Problem
• Multi Dimentional Knapsack Problem

Using

• C++ language
• nlohmann/json JSON parser for Modern C++

Requirements

• C++17 standard or more recent