Homework Help is Here – Start Your Trial Now!
Engineering
Data Structures and Algorithms
Please solve as soon as possible and use c++ for the Pseudo Code.

Please solve as soon as possible and use c++ for the Pseudo Code.

icon
Related questions
Question

Please solve as soon as possible and use c++ for the Pseudo Code. 

3. A thief robbing a store finds n items. The item is worth v, dollars and weighs w.pounds, where v, and y, 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 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 - 1 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 ($) Weight (lb) 1 5 3 1 3 10 5 3 4 15 5 4 4
Transcribed Image Text:3. A thief robbing a store finds n items. The item is worth v, dollars and weighs w.pounds, where v, and y, 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 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 - 1 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 ($) Weight (lb) 1 5 3 1 3 10 5 3 4 15 5 4 4
Expert Solution
steps

Step by step

Solved in 4 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer