Develop a dynamic programming algorithm for the knapsack problem: given n items of know weights w1, . . . , wn and values v1, . . . ,vn and a knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack. We assume that all the weights and the knapsack’s capacity are positive integers, while the item values are positive real numbers. (This is the 0-1 knapsack problem). Analyze the structure of an optimal solution. Give the recursive solution. Give a solution to this problem by writing pseudo code procedures. Analyze the running time for your algorithms.

Develop a dynamic programming algorithm for the knapsack problem: given n items of know weights w1, . . . , wn and values v1, . . . ,vn and a knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack. We assume that all the weights and the knapsack’s capacity are positive integers, while the item values are positive real numbers. (This is the 0-1 knapsack problem). Analyze the structure of an optimal solution. Give the recursive solution. Give a solution to this problem by writing pseudo code procedures. Analyze the running time for your algorithms.

Operations Research : Applications and Algorithms

4th Edition

ISBN:9780534380588

Author:Wayne L. Winston

Publisher:Wayne L. Winston

Chapter12: Review Of Calculus And Probability

Section12.5: Random Variables, Mean, Variance, And Covariance

Problem 5P

See similar textbooks

Similar questions

Question 2: Consider the 0/1 knapsack problem. Given Nobjects where each object is specified by a weight and a profit, you are to put the objects in a bag of capacity C such that the sum of weights of the items in the bag does not exceed Cand the profits of the items is maximized. Note that you cannot use an item type more than once. a. Using dynamic programming, write an algorithm that finds the maximum total value according to the above constraints. b. What is the complexity of your algorithm? c. Show the dynamic programming table for the following data: W= { 2 ,7 , 1} , P={ 3 ,15 , 2 } and C=8.
Using c++ Apply both breadth-first search and best-first search to a modified version of MC problem. In the modified MC, a state can contain any number of M’s and any number of C’s on either side of the river. Assume the goal is always to move all the persons on the left side to the right side. The Initial state should be a parameter given to the program at beginning of execution. As in the original problem, boat capacity =2, the boat cannot move by itself, and on either side C’s should not outnumber M’s. For best-first search, you need to come up with an appropriate heuristic. In addition to solving the problem, your grade will also be based on th effectiveness of the heuristic. As an example, the program should execute as follows. Initial state… Enter number of M’s on left side of the river: 3 Enter number of C’s on left side of the river: 1 Enter number of M’s on right side of the river: 0 Enter number of C’s on right side of the river: 0 Enter location of the boat: L The output…
Simulated annealing is an extension of hill climbing, which uses randomness to avoid getting stuck in local maxima and plateaux. a) As defined in your textbook, simulated annealing returns the current state when the end of the annealing schedule is reached and if the annealing schedule is slow enough. Given that we know the value (measure of goodness) of each state we visit, is there anything smarter we could do? (b) Simulated annealing requires a very small amount of memory, just enough to store two states: the current state and the proposed next state. Suppose we had enough memory to hold two million states. Propose a modification to simulated annealing that makes productive use of the additional memory. In particular, suggest something that will likely perform better than just running simulated annealing a million times consecutively with random restarts. [Note: There are multiple correct answers here.] (c) Gradient ascent search is prone to local optima just like hill climbing.…
a. Given n items, where each item has a weight and a value, and a knapsack that can carry at most W You are expected to fill in the knapsack with a subset of items in order to maximize the total value without exceeding the weight limit. For instance, if n = 6 and items = {(A, 10, 40), (B, 50, 30), (C, 40, 80), (D, 20, 60), (E, 40, 10), (F, 10, 60)} where each entry is represented as (itemIdi, weighti, valuei). Use greedy algorithm to solve the fractional knapsack problem. b. Given an array of n numbers, write a java or python program to find the k largest numbers using a comparison-based algorithm. We are not interested in the relative order of the k numbers and assuming that (i) k is a small constant (e.g., k = 5) independent of n, and (ii) k is a constant fraction of n (e.g., k = n/4). Provide the Big-Oh characterization of your algorithm.
The following problem is called the coupon collector problem and has many applications in computer science.Consider a bag that contains N different types of coupons (say coupons numbered 1 . . .N. There areinfinite number of each typ of coupon. Each time a coupon is drawn from the bag, it is independent of theprevious selection and equally likely to be any of the N types. Since there are infinite numbers of each type,one can view this as sampling with replacement. Let T denote the random variable that denotes the numberof coupons that needs to be collected until one obtains a complete set of atleast one of each type of coupon.Write a R simulation code to compute the E(T). Plot E(T) as for N = 10, 20, 30, 40, 50, 60. In the same plot show the theoretical value and summarize your observation regarding the accuracy of theapproximation.
The Knapsack Problem is a famous computer science problem that is defined as follows: imagine you are carrying a knapsack with capacity to hold a total of weight C. You are selecting among n items with values A={a_1, a_2, ... , a_n} and associated weights W={w_1, w_2, ... , w_n}. Here the weights and values are all positive (but not necessarily unique). You wish to maximize the total value of the items you select not exceeding the given weight capacity, i.e. maximize sum_{a in A} such that sum_{w in W} <= C. Please note that you can only select your items once. a) We can reformulate this as a 2D bottom-up dynamic programming problem as follows. Define T_{i,j} as the highest possible value sum considering items 1 through i and total weight capacity j (j <= C). What is the base case i.e. T_{0,j} for all j and T_{i,0} for all i?, and What is the loop statement?
3. A thief robbing a store finds n items. The i" item is worth v; dollars and weighs w; pounds, where v; and wi are integers. The thief wants to take as valuable a load as possible, but he can carry at most W pounds in his knapsack, for some integer W. Which items should he take? This problem is called 0-1 knapsack problem because for each item, the thief either take it or leave behind. No fractional amount from an item can be taken. Consider the most valuable load that weighs at most W pounds. If we remove item j from this load, the remaining load must be the most valuable load weighing at most W-w; that the thief can take from the n - I original items excluding j. Write a simple pseudo code for the given greedy algorithm description first and show how using this greedy algorithm to solve the problem of Knapsack problem below. Assume that maximum weight that can be carried is 7 lbs. Does it your code find the optimal solution? Show the optimal solution if it exists. Item Value ($)…
Consider the problem of making change for n cents using the fewest number of coins. Assume that we live in a country where coins come in k dierent denominations c1, c2, . . . , ck, such that the coin values are positive integers, k ≥ 1, and c1 = 1, i.e., there are pennies, so there is a solution for every value of n. For example, in case of the US coins, k = 4, c1 = 1, c2 = 5, c3 = 10, c4 = 25, i.e., there are pennies, nickels, dimes, and quarters. To give optimal change in the US for n cents, it is sufficient to pick as many quarters as possible, then as many dimes as possible, then as many nickels as possible, and nally give the rest in pennies. Design a bottom-up (non-recursive) O(nk)-time algorithm that makes change for any set of k different coin denominations. Write down the pseudocode and analyze its running time. Argue why your choice of the array and the order in which you ll in the values is the correct one.
Consider the problem of making change for n cents using the fewest number of coins. Assume that we live in a country where coins come in k dierent denominations c1, c2, . . . , ck, such that the coin values are positive integers, k ≥ 1, and c1 = 1, i.e., there are pennies, so there is a solution for every value of n. For example, in case of the US coins, k = 4, c1 = 1, c2 = 5, c3 = 10, c4 = 25, i.e., there are pennies, nickels, dimes, and quarters. To give optimal change in the US for n cents, it is sufficient to pick as many quarters as possible, then as many dimes as possible, then as many nickels as possible, and nally give the rest in pennies. Prove that the coin changing problem exhibits optimal substructure. Design a recursive backtracking (brute-force) algorithm that returns the minimum number of coins needed to make change for n cents for any set of k different coin denominations. Write down the pseudocode and prove that your algorithm is correct.
Consider the problem of making change for n cents using the fewest number of coins. Assume that we live in a country where coins come in k dierent denominations c1, c2, . . . , ck, such that the coin values are positive integers, k ≥ 1, and c1 = 1, i.e., there are pennies, so there is a solution for every value of n. For example, in case of the US coins, k = 4, c1 = 1, c2 = 5, c3 = 10, c4 = 25, i.e., there are pennies, nickels, dimes, and quarters. To give optimal change in the US for n cents, it is sufficient to pick as many quarters as possible, then as many dimes as possible, then as many nickels as possible, and nally give the rest in pennies. Design a bottom-up (non-recursive) O(nk)-time algorithm that makes change for any set of k different coin denominations. Write down the pseudocode and analyze its running time. Argue why your choice of the array and the order in which you fill in the values is the correct one. Notice how it is a lot easier to analyze the running time of…
Explain how to solve the {0, 1}-knapsack problem using dynamic programming. You are given n objects which cannot be broken into smaller pieces. Moreover, you have only one copy of each object. Each object i (where 1 ≤ i ≤ n) has an integer weight wi > 0 and a value vi > 0. You have a knapsack that can carry a total weight not exceeding W. Your goal is to fill the knapsack in a way that maximizes the total value of the included objects, while respecting the capacity constraint. For each object i (where 1 ≤ i ≤ n), either you bring it or not. 1. Write a recursion for the optimal solution and explain why it is correct. Make sure you define the notation you are using. 2. Consider the following input and fill the table corresponding to the recursion you found in #1: n = 6, w1 = 2, w2 = 2, w3 = 3, w4 = 2, w5 = 5, w6 = 4, v1 = 17, v2 = 2, v3 = 1, v4 = 1, v5 = 18, v6 = 11 and W = 12. Moreover, give all optimal solutions.
Exercise 4 20= 10+4+6 The rod-cutting problem consists of a rod of n units long that can be cut into integer-length pieces. The sale price of a piece i units long is Pi for i = 1,...,n. We want to apply dynamic programming to find the maximum total sale price of the rod. Let F(k) be the maximum price for a given rod of length k. 1. Give the recurrence on F(k) and its initial condition(s). 2. What are the time and space efficiencies of your algorithm? Now, consider the following instance of the rod-cutting problem: a rod of length n=5, and the following sale prices P1=2, P2=3, P3-7, P4=2 and P5=5.