README.md

In harjew/lab6G3: Computer lab 5

Lab 6

Author: Härje Widing

Install package

You can install this package fron github:

devtools::install_github("harjew/lab6G3")

library(lab6G3) library(microbenchmark)

The knapsack problem with 3 different solutions

The knapsack problem is a problem in combinatorial optimisation. Given that each item has a weight and a value, the problem is that you have backpack with a weight limit. You then want to maximize the value of the goods you can put in your backpack.

Knapsack brute force

The function algorithm knapsack brute force goes through all the possible answers to find the solution.This is the only solution that is guaranteed to give a correct answer. But it come with a cost of time and memory space. This approach calculates all the possible combinations that is 2^n. The calculated runtime is O(2^n).

Example:

x<-knapsack_data(16)

brute_force_knapsack(x,3500)

microbenchmark(brute_force_knapsack(x,3500),times=5)

Using parallel programming can make the code run faster and save a lot of time. By comparing the results we see that by parallel programming we see that the function becomes about twice as fast.

microbenchmark(brute_force_knapsack(x,3500,TRUE),times=5)

Dynamic programming

The dynamic approach saves the values already calculated, which implies that the code does not need to calculate the same equation more than once. The calculated runtime is O(nW), where n is the number of observations and W is the maximum weight limit.

Example:

x<-knapsack_data(500)

knapsack_dynamic(x,3500)

microbenchmark(knapsack_dynamic(x,3500),times=5)

Greedy heuristic

The Greedy approximation is to solve the inbounded knapsack problem. The Greedy heuristic algorithm will not give an exact result, it will return at least 50% of the true maximum value. The estimated runtime is estimated to O(nlog(n)).

Example:

x<-knapsack_data(1000000)

greedy_knapsack(x,3500,F)

microbenchmark(greedy_knapsack(x,3500),times=5)

harjew/lab6G3 documentation built on Nov. 4, 2019, 1:28 p.m.