Question

1. We have 5 objects, and the weights and values are
No.   1   2   3   4   5
w    10 20 30 40 50
v      20 30 66 60 55
The knapsack can carry a weight not exceeding 90, find a subset items and give the total weight and value for following algorithms:
1) By using the algorithm of greedy of value for 0-1 knapsack problem? By selecting the highest value first.
2) By using the algorithm of greedy of weight for 0-1 knapsack problem? By selecting lightest item first.
3) By using the algorithm of greedy of density for 0-1 knapsack problem? By selecting the highest density item first.
4) By using the algorithm of greedy of density for fractional knapsack problem? By selecting the highest density item first.

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

In this version of the problem we can either take an object or not (since it is 0-1 Knapsack). We sort the object in the non-increasing order by their values and we take the corresponding object as long as weight does not exceed 90.
This algorithm will take into knapsack: object 3, object 4, and object 2 (we notice it can’t take object 5 after object 4 because the maximum allowed weight would be exceeded).
The achieved weight is 30 + 40 +20 =90.
The achieved value is 66 + 60 + 30 = 156....

This is only a preview of the solution. Please use the purchase button to see the entire solution

Assisting Tutor

Related Homework Solutions

Kruskal Minimum Spanning Tree Algorithm Run on Example Graph
Homework Solution
$35.00
Benchmark
Report
Kruskal
Java
Report
Analysis
Complexity
Test
Case
Data
Problem
Critical
Operation
Comprehensive
Documentation
Approach
Lesson
Learned
Limitation
Expectation
Big-O
Graph
Input
Set
Introduction
Source
File
Code
M
5 Problems Involving Greedy Algorithms
Homework Solution
$50.00
Greedy
Algorithm
Analysis
Optimal
Program
Disk
Megabyte
Storage
Capacity
Decimalization
Denomination
Change-making
Half-crown
Florin
Shilling
Sixpence
Threepence
Pence
Coin
Solution
Selection
Sort
Framework
Decomposition
Egyptian
Computer Engineering Questions
Homework Solution
$4.00
Computer Science
Engineering
Intel 8086
Systems
DRAM Memory
RAS
Address Enable Signal
Processors
States
Reading
Writing
Propagation
Data Paths
Time Requirements
Clocking Rate
Access Time
Floyd-Warshall's Algorithm - Behavioral Analysis
Homework Solution
$50.00
Floyd
Warshall
Algorithm
Analysis
Java
Benchmark
Directed
Weighted
Graph
Complexity
Big-O
Documentation
Computer Science
Data Structures
Algorithms
Get help from a qualified tutor
Live Chats