Scribd Logo
Upload

Welcome to Scribd!

  • 4K views

    Knapsack Problem Using Backtracking

    Uploaded by

    Pandia Raj
    The document describes the knapsack problem and its solution using backtracking (branch and bound). It defines the problem as selecting a subset of weights that maximizes total profit, given weights, profits, and a knapsack capacity. The solution space is examined recursively using bounding functions to prune suboptimal solutions. An algorithm is provided that assigns weights and profits in descending order of ratio, checks if each weight fits in the knapsack, and calculates an upper bound on profit at each step to guide pruning.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd

    Knapsack Problem Using Backtracking

    Uploaded by

    Pandia Raj
    4K views11 pages
    The document describes the knapsack problem and its solution using backtracking (branch and bound). It defines the problem as selecting a subset of weights that maximizes total profit, given weights, profits, and a knapsack capacity. The solution space is examined recursively using bounding functions to prune suboptimal solutions. An algorithm is provided that assigns weights and profits in descending order of ratio, checks if each weight fits in the knapsack, and calculates an upper bound on profit at each step to guide pruning.

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes the knapsack problem and its solution using backtracking (branch and bound). It defines the problem as selecting a subset of weights that maximizes total profit, given weights, profits, and a knapsack capacity. The solution space is examined recursively using bounding functions to prune suboptimal solutions. An algorithm is provided that assigns weights and profits in descending order of ratio, checks if each weight fits in the knapsack, and calculates an upper bound on profit at each step to guide pruning.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    4K views11 pages

    Knapsack Problem Using Backtracking

    Uploaded by

    Pandia Raj
    The document describes the knapsack problem and its solution using backtracking (branch and bound). It defines the problem as selecting a subset of weights that maximizes total profit, given weights, profits, and a knapsack capacity. The solution space is examined recursively using bounding functions to prune suboptimal solutions. An algorithm is provided that assigns weights and profits in descending order of ratio, checks if each weight fits in the knapsack, and calculates an upper bound on profit at each step to guide pruning.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 11

    KNAPSACK PROBLEM USING BACKTRACKING

    (BRANCH AND BOUND)

    • Problem Definition

    • Solution

    • Algorithm

    • Example

    • Time complexity
    Problem Definition
    • We are given n objects and a knapsack or bag. The objective is to
    obtain a filling of the knapsack that maximizes the total profit
    earned.

    Given

    – n = number of weights

    – w = weights

    – P =profits m= knapsack capacity


    The problem is similar to the zero-one (0/1) knapsack optimization
    problem is dynamic programming algorithm.
    • We are given ‘n’ positive weights Wi and ’n’ positive
    profits Pi, and a positive number ‘m’ that is the
    knapsack capacity, the is problem calls for choosing a
    subset of the weights such that,
    Solution Space
     
    • The Solution space is the same as that for the sum of subset’s
    problem.
    • Bounding functions are needed to help kill some live nodes without
    expanding them.
    • A good bounding function for this problem is obtained by using an
    upper bound on the value of the best feasible solution obtainable
    by expanding the given live node.
    • The profits and weights are assigned in descending order depend
    upon the ratio.

    (i.e.) Pi/Wi P(I+1) / W(I+1)


    Solution
    • After assigning the profit and weights, we have to take the first object
    weights and check if the first weight is less than or equal to the
    capacity, if so then we include that object (i.e.) the unit is 1.(i.e.) K
    1.

    • Then We are going to the next object, if the object weight is exceeded
    that object does not fit. So unit of that object is ‘0’.(i.e.) K=0.

    • Then We are going to the bounding function, this function determines


    an upper bound on the best solution obtainable at level K+1.

    • Repeat the process until we reach the optimal solution.


    Algorithm
    • It determines an upper bound on the best solution
    obtainable by expanding any node Z at level K+1 of
    the state space tree.
    • The object weights and profits are w[i] and p[i].

    • It is assumed that p[i]/w[i] >= p[i+1]/w[i+1]


    Algorithm
    • 1. Algorithm BKnap( cp, cw, k)
    • 2. //cp is the current profit, cw is the current wt total, k is the index of last
    • removed item and m is the knapsack size
    • 3. {
    • 4. b := cp; c := cw;
    • 5. for i:= k+1 to n do
    • 6. {
    • 7. c:= c + w[ i ];
    • 8. if ( c < m) then b:= b + p[ i ] ;
    • 9. else return b+( 1- (c-m)/ w[ i ]*p[ i ];
    • 10. }
    • 11. return b;
    • 12. }
    Example
    Time complexity

    You might also like