Project 2 Final Report: Comparing Knapsacks Experiment

For the structure we chose to use the template you provided for us in the project as each one of us would have our own classes that the others shouldn’t be making any edits on, so this would help us avoid merge conflicts where we could. We also came to an agreement that having the knapsack saved as an object would be the best approach, as we could input our data and manipulate it to fit each of our methods parameters. We added a ProjectTools package that holds any other classes, that aren't the knapsack classes themselves, to use in our project. As for graphing, unlike the last project, we decided to try and make the graphs in java ourselves so we wouldn't need to use anything other than intelliJ to complete the project.

As for the metric we chose to use runtime again. We made this choice because it was an easy implementation since we used it for our last project, and also because the runtime of the algorithm is easy to understand, explain, and can directly show how efficient each algorithm is. As for how our results will be displayed we have each of our methods printing out what weights and values were used, what knapsack number it is, the weight capacity, the total weight that we used, and the maximum profit onto the console while it is running. Then we have our class PlotGenerator that will display the runtimes as a graph, to do this we used a Java library called JFreeChart.

UML Diagram

Plot Charts

Author: Cheryl Moser

Performance Analysis

Fractional Dynamic VS 01 Dynamic: Author: Mycole Brown

K01 Dynamic Programming method is inconclusive.

Fractional Dynamic VS Fractional Greedy: Author: Mycole Brown

The graph for the Fractional Greedy algorithm shows a runtime that starts high and quickly drops, stabilizing at a low level as the input array size increases.

The Fractional Dynamic algorithm graph also starts high and decreases rapidly, but appears to stabilize slightly higher than the Greedy algorithm.

Fractional Dynamic VS 01Greedy: Author: Mycole Brown

The 0/1 Greedy algorithm graph shows a sharp decrease and then stabilizes at a higher time than the Fractional Dynamic algorithm, suggesting that the Fractional Dynamic is more efficient for larger input sizes.

Fractional Dynamic VS Fractional Brute: Author: Mycole Brown

The Fractional Brute Force graph shows a very steep climb as the input size increases, indicating a significant increase in runtime, likely exponential.

In contrast, the Fractional Dynamic algorithm maintains a lower and more stable runtime, even as the input size grows, marking it as significantly more efficient than the Brute Force method.

From these comparisons, we can say that the Fractional Dynamic algorithm is more efficient than the Fractional Greedy and 0/1 Greedy algorithms for larger input sizes and much more efficient than the Fractional Brute Force algorithm, which has a runtime that increases exponentially with the input size. The Greedy versions of the algorithms are usually faster for smaller input sizes but do not scale as well as the Dynamic version when the input size gets larger.

Fractional Dynamic VS 01 Brute: Author: Angela Fujihara
How it Works:: This method checks every possible combination of items, making it very slow, especially with larger datasets.
Time Complexity:: The time complexity of Brute Force 0/1 Knapsack is exponential, typically represented as O(2ⁿ), where 'n' is the number of items. This means that as 'n' increases, the time taken to find the optimal solution grows exponentially.
Execution Time:: With small sets of items (like 5 or 10), it's relatively fast, taking anywhere from no time at all to about 10 milliseconds. But as the number of items increases, it can get really slow. For sets of 15 to 20 items, it takes between about 20,000 to 180,000 microseconds. And for sets of 25 or 30 items, it gets so slow that we can't even measure it accurately.
How it Works:: This method sorts items by value-to-weight ratios before picking them, which makes it faster than brute force.
Time Complexity:: The time complexity of Fractional Dynamic Knapsack is O(n log n), where 'n' is the number of items. This complexity arises from sorting the items by their value-to-weight ratios before selecting them, which enhances efficiency compared to the brute force approach.
Execution Time:: Unlike brute force, Fractional Dynamic Knapsack stays consistently fast no matter how many items you have. For sets of 5 to 30 items, it takes about 250 to 500 microseconds most of the time. This shows that it handles larger sets of items without slowing down much.
Conclusion:: Comparing the two methods using the provided data and considering their time complexities, Fractional Dynamic Knapsack remains the preferred choice. While Brute Force 0/1 Knapsack struggles with larger datasets due to its exponential time complexity, Fractional Dynamic Knapsack maintains a more consistent and efficient performance, demonstrating its superiority in handling larger sets of items.

Fractional Greedy VS Fractional Brute: Author: Angela Fujihara
How it Works:: Greedy Fractional Knapsack selects items based on their value-to-weight ratio, choosing the most valuable items first until the knapsack is full.
Time Complexity:: Greedy Fractional Knapsack has a time complexity of O(n log n), meaning it's pretty efficient even for large datasets. This complexity arises from sorting the items by their value-to-weight ratios before selecting them.
How it Works:: Brute Force Fractional Knapsack considers all possible combinations of items to find the best solution, which can take a long time.
Time Complexity:: The time complexity of Brute Force Fractional Knapsack is exponential, typically represented as O(2ⁿ), where 'n' is the number of items. This means that as 'n' increases, the time taken to find the optimal solution grows exponentially.
Conclusion:: The Greedy Fractional Knapsack algorithm works better overall. It's fast and consistent across different dataset sizes, whereas the Brute Force approach slows down a lot as the dataset gets bigger. Additionally, Greedy Fractional Knapsack's time complexity suggests it's efficient even for larger datasets, making it a preferable choice in most cases.

Fractional Greedy VS 01 Brute: Author: Angela Fujihara
How it Works:: Brute Force 0/1 Knapsack checks every possible combination of items, which can take a lot of time, especially with more items.
Time Complexity:: The time complexity of Brute Force 0/1 Knapsack is exponential, typically represented as O(2ⁿ), where 'n' is the number of items. This means that as 'n' increases, the time taken to find the optimal solution grows exponentially.
How it Works:: Greedy Fractional Knapsack picks items with the best value- to-weight ratio first until the knapsack is full.
Time Complexity:: Greedy Fractional Knapsack has a time complexity of O(n log n), making it efficient even for larger datasets. This complexity arises from sorting the items by their value-to-weight ratios before selecting them.
Conclusion:: Based on the data and considering how long they take, Greedy Fractional Knapsack is faster. It stays speedy across different dataset sizes, while Brute Force 0/1 Knapsack slows down a lot as the dataset gets bigger. Greedy Fractional Knapsack seems like a better choice when you need a quick and decent solution. But keep in mind, the Greedy approach isn't always perfect. Sometimes it might not give the best answer, especially if the problem is more complicated. So, while Greedy Fractional Knapsack is fast and handy, it might not always give you the absolute best solution.

Fractional Greedy VS 01 Greedy: Author: Angela Fujihara
How it Works:: Greedy Fractional Knapsack selects items based on their value-to-weight ratio, prioritizing those with the best ratio until the knapsack is full.
Time Complexity:: Greedy Fractional Knapsack has a time complexity of O(n log n), ensuring efficiency even with larger datasets. It sorts items by their value-to-weight ratios before selection.
How it Works:: Greedy 0/1 Knapsack prioritizes the most valuable items first, assessing whether each fits entirely into the knapsack.
Time Complexity:: Greedy 0/1 Knapsack's time complexity depends on implementation but generally handles larger datasets reasonably well. While it doesn't sort items like the Fractional Knapsack, it maintains efficiency without significant slowdowns.
Conclusion:: Considering the execution times and time complexities, both Greedy Fractional Knapsack and Greedy 0/1 Knapsack perform well, particularly with smaller datasets. Greedy Fractional Knapsack exhibits consistent speed across all dataset sizes, while Greedy 0/1 Knapsack slightly increases in time with larger datasets. Overall, Greedy Fractional Knapsack appears to handle larger datasets more efficiently, making it preferable in many cases.

Comparison Note for Brute Force

The runtimes for both brute force methods up to knapsack #4 are A LOT less than 5,000,000 Microseconds, but due to the exponentially high runtime of knapsack #6 it is hard to say what the number actually is)

01 dynamic vs 01 greedy

Author: Ashtin Rivada

K01 Dynamic Programming method is inconclusive.

Fractional Brute vs 01 Greedy

Author: Ashtin Rivada

Knapsack #1: 9,500 Microseconds
Knapsack #2: about 650 Microseconds
Knapsack #3: about 800 Microseconds
Knapsack #4: about 1,100 Microseconds
Knapsack #5: about 1,250 Microseconds
Knapsack #6: about 1,400 Microseconds

Knapsack #1: Less than 5,000,000 Microseconds
Knapsack #2: Less than 5,000,000 Microseconds
Knapsack #3: Less than 5,000,000 Microseconds
Knapsack #4: Less than 5,000,000 Microseconds
Knapsack #5: about 5,000,000 Microseconds
Knapsack #6: about 130,000,000 Microseconds

Comparison

We can see there is a clear winner in which method ran faster. That would be the Greedy for the 01 Knapsack. It is very fast and does not change the runtime much, even for the bigger datasets that Brute force takes forever to finish. I am assuming the first knapsack for 01 Greedy took much longer than the rest probably due to all the initializations going through for the first call but those would not have to be made for the following tests as they were made in the first and would just need to be updated.

Fractional Brute vs 01 Brute

Author: Ashtin Rivada

----------01 Brute Speeds----------

Knapsack #1: Less than 2,500,000 Microseconds
Knapsack #2: Less than 2,500,000 Microseconds
Knapsack #3: Less than 2,500,000 Microseconds
Knapsack #4: Less than 2,500,000 Microseconds
Knapsack #5: about 2,700,000 Microseconds
Knapsack #6: about 54,000,000 Microseconds

----------Fractional Brute Speeds----------

Knapsack #1: Less than 5,000,000 Microseconds
Knapsack #2: Less than 5,000,000 Microseconds
Knapsack #3: Less than 5,000,000 Microseconds
Knapsack #4: Less than 5,000,000 Microseconds
Knapsack #5: about 5,000,000 Microseconds
Knapsack #6: about 130,000,000 Microseconds

Comparison

Both the Brute force method for the 01 Knapsack and for the Fractional Knapsack look similar. Each method can solve up to size 20 pretty fast, remaining very close to the x-axis. Then when we start on Knapsack #5 which has 25 items we start to see a slight increase for both methods for their runtime. With the 01 knapsack reaching about 2,700,000 microseconds and the fractional reaching about 5,000,000. Finally we get to knapsack #6 which has 30 items so the number of combinations increases exponentially. We have the 01 knapsack running at about 54,000,000 and fractional running at about 130,000,000. We can see here that once the brute force reaches a certain point it takes a very long time to finish. The 01 brute force ran about 2x as fast as the fractional probably due to not having to ratio any items to make sure all of the maximum weight was taken up. With this being said The brute force approach would not be ideal for larger dataSets as the runtime would increase exponentially.

Fractional Brute vs 01 Dynamic: Author: Ashtin Rivada

K01 Dynamic Programming method is inconclusive.

01 Dynamic VS Fractional Greedy: Author: Cheryl Moser

K01 Dynamic Programming method is inconclusive, though it currently shows as being one of the best performers of the bunch with even the largest input size keeping a runtime of under 24 microseconds. FracK Greedy seems to be the clear winner here, with very low runtimes that hold steady across all input sizes.

01 Dynamic VS 01 Brute: Author: Cheryl Moser

K01 Dynamic Programming method is inconclusive, though it currently shows as being one of the best performers of the bunch with even the largest input size keeping a runtime of under 24 microseconds. 01 Brute shows a steep exponential curve, as expected.

01 Greedy VS 01 Brute: Author: Cheryl Moser

It seems that several algorithm plots begin with an outlier point. I suspect this is due to a slowdown caused by the initialization that happens as the code enters a new algorithm class. I confirmed that the array size of 5 is not the issue by placing the array of size 30 into the first plot point generation, and the array of size 5 into the last. The graph still showed that first outlier point. I conducted this test for the K01 Greedy algorithm only.

Discarding the first plot point, greedy performed better across the board in this comparison, holding steady between 800 - 2100 ms for all array sizes. The greedy plot appears to be a curve resembling an O(n log n) curve, though that is somewhat inconclusive without more data points to the right; the brute force plot shows an exponential curve.

Theoretical results vs empirical results

Author: Cheryl Moser

Theoretical

Brute Force --> Expectation: O(2ⁿ) for both K01 & FracK
Greedy --> O(n log n) for both K01 & FracK; however, we know that it may produce suboptimal results when applied to K01
Dynamic Programming --> 01 O(nW), where W = the weight limit of the knapsack | FracK exponential similar to O(2ⁿ)

Empirical

Brute Force --> Results match expectations for both knapsacks
Greedy --> Results match expectations for both knapsacks
Dynamic Programming --> 01 (inconclusive) | FracK low exponential

Conclusion

Results were as expected for brute force and greedy: brute force displayed a curve that was extremely steep as it progressed toward larger arrays; greedy displayed a slow, steady rise as arrays became larger, with a faster performance when applied to the fractional knapsack. More data points of large array sizes are needed to determine if the shape of the curve indeed looks like the expected O(n log n). The surprise result lies with the dynamic programming method as applied to the fractional knapsack, as it did indeed display as exponential, but far less than the expected O(2ⁿ).

Which algorithm performed best for which knapsack?

0/1 Knapsack:

Why Greedy is Best: The Greedy approach is effective for the 0/1 Knapsack problem because it prioritizes immediate gains. It quickly selects items with the highest value-to-weight ratio, filling the knapsack until capacity is reached. Although it may not always find the optimal solution, it generally provides a good approximation efficiently. In contrast, the brute-force method exhaustively evaluates all combinations, becoming prohibitively slow as the dataset size increases.

For Fractional Knapsack:

Why Dynamic Programming and Greedy are Best:

Dynamic Programming (Fractional Knapsack):
This approach excels, particularly for larger tasks. It breaks down the problem into smaller, manageable parts and efficiently combines their solutions without sacrificing efficiency.

Greedy (Fractional Knapsack): Greedy remains a viable choice, especially for smaller datasets. It prioritizes items with the best value-to-weight ratio, adding them to the knapsack incrementally. While it may not always yield the optimal solution, its speed and reliability make it a practical option for smaller-scale problems.

Conclusion:

In conclusion, Dynamic Programming and Greedy algorithms stand out as the top contenders for Fractional Knapsack problems. Dynamic Programming's systematic approach to problem-solving and efficient solution recombination make it ideal for larger datasets. On the other hand, Greedy offers speed and reliability, making it a suitable choice for smaller-scale tasks. For 0/1 Knapsack problems, Greedy strikes a balance between efficiency and accuracy, making it the preferred method over the brute-force approach.

Algorithm development

Brute force method for the fractional knapsack problem: Author: Angela Fujihara

The methodology involves iterating through all possible combinations of items and calculating the total value and weight for each combination. It ensures accuracy by considering every possible combination but may be inefficient for large datasets due to its exponential time complexity.
Greedy method for the fractional knapsack problem: Author: Angela Fujihara

The methodology involves sorting the items based on their value-to-weight ratio and iteratively selecting the items with the highest ratio until the knapsack's capacity is reached. It prioritizes items with the highest immediate benefit, aiming to maximize the total value of items in the knapsack. However, it may not always yield the optimal solution.
Greedy method for the knapsack 0-1 problem: Author: Cheryl Moser; Description: This method is a modified version of the greedy method for the fractional knapsack. It is not guaranteed to return optimal results, especially with larger input arrays. The greedy method for this problem is not optimal because it does not consider all combinations of items; instead, it puts items into the knapsack sequentially by highest value-to-weight ratio until the weight limit is met.

Methods: A priority queue was used in combination with a custom comparator for holding value-weight pairs in non-increasing order by the value/weight ratio. A hash set was used to store the items that were added to the knapsack. The method iterates through the priority queue, removing the highest value-to-weight entry first and adding it to the knapsack until the queue is empty, or until the weight limit is met. If the addition of an item exceeds the weight limit, it is discarded and the next item is considered.

Analysis: The time complexity of this method is O(n log n). This is due to the dequeue operation nested within the priority queue iterator operation. The iterator operation depends on the length of the priority queue, or the weight limit, either of which can be of any size; the dequeue operation involves a re-ordering of the queue, which is O(log n) due to the halving operations done on the binary heap.
01 Brute Force: Author: Ashtin Rivada

My process for developing my algorithm came after a bunch of research. My first approach was using recursion to get all possibilities of combinations but this seemed to have optimized my method, as I ran it and it solved all the tests too fast to be considered a true brute force method. This made me take some time and try to come up with a way to get all combinations without using any recursion. I concluded that making each weight and value pair an item of itself would make it easier for comparison and combinations.Then after some time researching I found a Java library that could get these combinations for me without optimizing my brute force. To make this work I needed a Set of Items rather than the array of Items I was originally using so I converted this to the set and was able to use a method from a java library called “Sets.powerSet”. This gave me all the possible combinations and from the inputted set of items, then I looked through each combination making sure the total weight the combination had was under the maximum weight allowed and if this was true I checked if the total profit was greater than what I currently had and if it was, it was now our new total profit. After they are all checked the one with the greatest profit while also staying within the allowed weight range was saved as my best choice and I was able to use that to print my answers into the console.

Were there any other algorithms that could have solved these problems? Such as divide-and-conquer?

Greedy Methodology (0/1 and Fractional): The greedy approach to the knapsack problem involves making the locally optimal choice at each step with the hope of finding the global optimum. For the 0/1 knapsack, this might involve choosing items based on value-to-weight ratio without splitting items. For the fractional knapsack, it allows splitting items to maximize the total value within the weight constraint.
Dynamic Programming (Fractional Dynamic): Dynamic programming solves problems by breaking them down into simpler subproblems. It is used to solve the knapsack problem by considering the solution for smaller capacities and smaller sets of items, then building up to the solution for the original problem. It typically involves using a table to store the results of subproblems to avoid redundant calculations.
Brute Force Methodology (Fractional Brute Force): A brute force approach checks all possible combinations of items to find the one that offers the most value without exceeding the weight limit. This method is exhaustive and often impractical for large datasets due to its exponential time complexity.
Divide and Conquer: This approach involves dividing the problem into smaller subproblems, solving the subproblems recursively, and then combining their solutions to solve the original problem. While divide-and-conquer is a powerful strategy for many problems, it is not typically used for the knapsack problem because the knapsack problem does not naturally break down into independent subproblems that can be solved recursively without overlapping subproblems, which is where dynamic programming is more efficient.
Genetic Algorithms: These are adaptive heuristic search algorithms that are based on the evolutionary ideas of natural selection and genetics. What does heuristic mean? Imagine you're in a maze. Instead of wasting time trying every possible path from start to finish, you follow a simple rule like 'always turn right' to find the exit. It's not foolproof, but it gets you out quickly. That’s what a heuristic does in problem-solving: it's a shortcut that’s usually good enough. They are particularly useful for solving optimization and search problems where the solution space is large and complex.
Simulated Annealing: This is a probabilistic technique and it’s used for estimating the global optimum of a given function.What is a probabilistic technique? A probabilistic technique in the context of algorithm design is a method that makes use of randomness as part of its logic or process. It doesn't guarantee a perfect answer every time but is designed to find a good answer most of the time. Probabilistic algorithms often perform well for complex problems where deterministic solutions (those that are always expected to produce the same result) might be too slow or difficult to implement. What is a global optimum? You're playing hide and seek, and you want to find the absolute best hiding spot in the entire area. The global optimum is that unbeatable spot. Finding it means you've won the game of hide and seek in the most spectacular way possible. Out of all of the places it’s the most optimum (assuming that's correct English). It is a metaheuristic to approximate global optimization in a large search space and can be applied to the knapsack problem. What is a metaheuristic? This is like having a bunch of different 'always turn right' rules and picking the one that seems to work best for the particular maze you're in. It's a strategy to choose between different shortcuts. Also a search space needs some defining. A search space is all the spots you could possibly hide in during the game of hide and seek. Some spots are pretty good, some are okay, and one is the ultimate best. That's your search space.
The name “simulated annealing” comes from how blacksmiths make swords. They heat metal to make it malleable, hammer it into shape, and then cool it down to lock in the form. Simulated annealing does something similar with solutions – it shakes things up with heat (randomness) to escape ruts and then cools down to settle into a great solution.
Backtracking: This is an algorithmic technique for solving problems recursively by trying to build a solution, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point in time.
Branch and Bound: This is another algorithm design paradigm used for solving combinatorial optimization problems like the knapsack problem. Combinatorial optimization problems are puzzles where you have to consider a bunch of different elements and figure out the best combination. Like choosing your team in a pick-up basketball game from everyone who showed up at the court. It involves dividing the problem into several branches, computing bounds for each branch, and then pruning branches that cannot yield better solutions than the best one found so far.

Name		Name	Last commit message	Last commit date
Latest commit History 52 Commits
Git Screenshots		Git Screenshots
images		images
src		src
test		test
.gitignore		.gitignore
PROJECTSPEC.md		PROJECTSPEC.md
README.md		README.md

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Repository files navigation

Project 2 Final Report: Comparing Knapsacks Experiment

Table of Contents

How to run this application

Add jar files:

Run both driver classes:

Authors and Contributions

Project Description

UML Diagram

Plot Charts

Performance Analysis

Theoretical results vs empirical results

Which algorithm performed best for which knapsack?

Algorithm development

Were there any other algorithms that could have solved these problems? Such as divide-and-conquer?

Some different methodologies for solving the knapsack problem:

Other algorithms that could have been used to solve these problems

About

Uh oh!

Releases

Packages

Contributors 4

Uh oh!

Languages

moserc/knapsack-experiment

Folders and files

Latest commit

History

Repository files navigation

Project 2 Final Report: Comparing Knapsacks Experiment

Table of Contents

How to run this application

Add jar files:

Run both driver classes:

Authors and Contributions

Project Description

UML Diagram

Plot Charts

Performance Analysis

Theoretical results vs empirical results

Which algorithm performed best for which knapsack?

Algorithm development

Were there any other algorithms that could have solved these problems? Such as divide-and-conquer?

Some different methodologies for solving the knapsack problem:

Other algorithms that could have been used to solve these problems

About

Resources

Uh oh!

Stars

Watchers

Forks

Releases

Packages 0

Contributors 4

Uh oh!

Languages

Packages