• Login
    View Item 
    •   Carroll Scholars Home
    • Mathematics, Engineering and Computer Science
    • Mathematics, Engineering and Computer Science Undergraduate Theses
    • View Item
    •   Carroll Scholars Home
    • Mathematics, Engineering and Computer Science
    • Mathematics, Engineering and Computer Science Undergraduate Theses
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Heuristics for the Knapsack Problem

    Thumbnail
    View/Open
    2008_GilbertsonC_THS_000642.pdf (7.953Mb)
    Author
    Gilbertson, Claire
    Advisor
    Holly Zullo; Mark Parker; Jeffrey Morris
    Date of Issue
    2008-04-01
    Metadata
    Show full item record
    URI
    https://scholars.carroll.edu/handle/20.500.12647/3431
    Title
    Heuristics for the Knapsack Problem
    Type
    thesis
    Abstract
    We explore the knapsack problem where the goal is to maximize the value of packed objects for a certain container. The knapsack problem is NP-complete which means the time needed to solve it exactly grows exponentially as the size of the data set increases. Due to the infeasibility of using algorithms which find all possible solutions, we can use heuristics which are methods used to estimate a solution rapidly. We create a Java program to test seven heuristics on 21 data sets. The seven packing algorithms include four basic greedy algorithms, two backtracking methods, and one random packer. We use data sets from a standard library and create our own data sets with specific characteristics. The greedy algorithm which sorts by largest utility and the one of the backtracking methods perform the best.
    Degree Awarded
    Bachelor's
    Semester
    Spring
    Department
    Mathematics, Engineering & Computer Science
    Collections
    • Mathematics, Engineering and Computer Science Undergraduate Theses

    Browse

    All of Carroll ScholarsCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    DSpace software copyright © 2002-2023  DuraSpace
    DSpace Express is a service operated by 
    Atmire NV