Skip to content

Latest commit

 

History

History
executable file
·
32 lines (23 loc) · 1.54 KB

README.md

File metadata and controls

executable file
·
32 lines (23 loc) · 1.54 KB
Raw

Vanilla Knapsack and Its Various Flavors

The Robber Knows You

Introduction

This project explores different approach to the familiar Maximum 0-1 Knapsack problem:

  • Maximum Value Dynamic Programming
  • Minimum Cost Dynamic Programming
  • Greedy 2-Approximation
  • Fully Polynomial-time Approximation Scheme

As a side experiment, we attempt to reduce 3SAT to Decision 0-1 Knapsack problem.

Usage

To run the experiment, use the build script. You can modify various run settings by modifying config.properties. This script also helps building the report written in R. To modify the rendering of the report, refer to configs.R. Make sure that you run the script directly, i.e. launch it from the directory it belongs to.

./build.sh

The report comes in 2 different formats: PDF, HTML (gitbook, bookdown). To view the HTML version, you can view this file or for better functionality, we recommend using the start script which serves the HTML files at a local server, i.e. localhost:2302, on your machine (with this, you can use the search function within the document).

./start.sh

The default port is 2302, which can be changed by modifying configs.R.

Structure

  • data: result of the experiments (in CSV and TXT).
  • document: the report on result of the experiments.
  • src: source codes for the project (Java and R).