Skip to content

We made a bounded knapsack problem in algorithms. I was curious in figuring out an unbounded knapsack and backtracking

Notifications You must be signed in to change notification settings

lepsch22/Unbounded_Knapsack_Itterative

Repository files navigation

in the ThanksGivingAlgorithm. This method has everything going on inside of it, in terms of calculating everything needed. Because this problem is a unbounded knapsack problem we will use dynamic programming. First we have 4 parameters to pass in. The weight, name, and enjoyment of foods and the stomach capacity. First we create the matrix where we will keep track of all enjoyment values given each capacity in increments of 1. SO if we have a capacity of 30 it will be 1,2,3,4,...,30 for the amount of columns then for the rows we will have each food. What is important about this matrix is for each row in the same column we check to see if the previous row value is greater than the one we currently have. The actual value stored in there is a product from this equation Math.max(WEC[i - 1][j], WEC[i][j - weight[i-1]] + enjoy[i-1]) . What this equation does is if the weight of our food item is greater than the capacity then use this equation. The first part is checking the previous row value. The second part takes the valueOf((capacity - the weight of the current item) + (enjoyment of the current item)). if the algorithm does not make sense there are many YouTube videos on it. While this is going on we are also keeping track of when we use a food item. When we find that we can add a new food item we will add it to a matrix made the same we and traversed the same way as the enjoyment matrix. Finally after we traverse both matrices the last row last column output will hold our answers. The optimal enjoyment is just printed out, and then the string that contains the foods used is then converted to a user friendly string that shows the amount of each food.

About

We made a bounded knapsack problem in algorithms. I was curious in figuring out an unbounded knapsack and backtracking

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages