Skip to content

This repository includes a study that aims to handle the knapsack problem with recursive-methods and dynamic-programming paradigm. Detailed info in ReadMe

License

Notifications You must be signed in to change notification settings

asrinoztin/knapsack

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

3 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Instructions

Imagine a thief entering a house. In the house, there are infinitely many itemsthat can have only one of three different weights: 1 kg, 3 kgs, and 5 kgs. All of the items are discrete. The thief has a bag capacity of n kgs and strangely, he wants to steal the “smallest number of items”.You need to implement a mathematical recursive formulation for C(n) where C(n) denotes the smallest number of items the thiefcan steal using a bag capacity of n.

(a) Implement a recursive algorithm that returns the smallest number of items the thief can steal using a bag capacity of n.

(b) Implement a dynamic programming algorithm for finding the smallest number of items the thief can steal using a bag capacity of n.

(c) Compare your results.

Results

Ekran görüntüsü 2022-01-25 024524

Figure_1

Related Problems

(Source: https://leetcode.com/discuss/general-discussion/1000929/solved-all-dynamic-programming-dp-problems-in-7-months)

https://leetcode.com/problems/house-robber-ii/
https://leetcode.com/problems/ones-and-zeroes/
https://leetcode.com/problems/target-sum/
https://leetcode.com/problems/shopping-offers/
https://leetcode.com/problems/2-keys-keyboard/
https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/
https://leetcode.com/problems/best-team-with-no-conflicts/
https://leetcode.com/problems/profitable-schemes/
https://leetcode.com/problems/tallest-billboard/
https://leetcode.com/problems/pizza-with-3n-slices/
https://leetcode.com/problems/reducing-dishes/

About

This repository includes a study that aims to handle the knapsack problem with recursive-methods and dynamic-programming paradigm. Detailed info in ReadMe

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages