Skip to content
This repository has been archived by the owner on Jan 18, 2022. It is now read-only.

Latest commit

 

History

History
73 lines (52 loc) · 2.95 KB

README.md

File metadata and controls

73 lines (52 loc) · 2.95 KB
Raw

Data storage with the Multiple Knapsack Problem (MKP)

This project was made as a school project in order to find how to solve a Multiple Knapsack Proble

Solution

graph example

MKP

here:

  • The collections (Knapsacks) are the SystemNodes;
  • The items to place in are the Data;
  • The weight of each item is size of the Data;
  • The max weight of the collection is the capacity of the SystemNode;
  • The value of each item is the inverse of the quadratic mean of weighted distances from all users that are interested in the data;

My way to solve it

As in the MKP, the objective is to pick some of the items, with maximal total profit p, while obeying that the maximum total weight w of the chosen items that must not exceed the max weight W of each collection. As the project involve an MKP, we place data on the node where it have the best profit and the solve single nodes as a 0-1 knapsack problem. Then we take items that not fit in the collection and loop the algorithm removing already filled nodes.

Getting Started

These instructions will get you a copy of the project up and running on your local machine for development and testing purposes. See deployment for notes on how to deploy the project on a live system.

Prerequisites

To be able to run the project, you need to have java 8 or upper installed and as well as maven

Running the project

You first need to clone the project

git clone git@github.com:nowtryz/data-storage.git
cd data-storage

From command line

To run the project, follow the steps bellow:

  • package the app with maven 
    mvn clean package
  • run the archive 
    java -jar taget/data-storage-1.0-SNAPSHOT.jar

From IntelliJ

Open the .iml module

Built With

  • Maven - Dependency Management
  • JGraphT - Used to manipulate graphs

Versioning

We use SemVer for versioning. For the versions available, see the tags on this repository.

License

This project is licensed under the MIT License