Chapter 27 Flashcards
What is fractional knapsack problem
In the 0-1 Knapsack problem, we are not allowed to break items. We either take the whole item or don’t take it.
In Fractional Knapsack, the setup is exactly the same but we can break items for maximizing the total value of knapsack.
what is knapsack problem
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
Can we solve fractional knapsack problem with greedy algorithm and it is optimal
Yes
What is row eye
Price/weight = answer is row eye for that data set
Can we solve knapsack problem with greedy algorithm and is it optimal
We can solve knapsack problem with greedy algorithm but its not optimal
What gives optimal solution in knapsack problem
Dynamic programming
When we can built graph
In a condition when:
- A set of objects
- relationship between objects
What are example of graphs
computer and communicate network, transport network, GIS, VLSI (very large scale integration) etc
If we have ordered pair then we will have directed graph. True or False
True
If we have unordered pair then we will have undirected graph. True or False
True
What are types of graphs
Graph, digraph and multi graph
What is digraph
directed graph
What is adjacent vertices
A vertex W is adjacent to vertex V if there is an edge from V to W
What is incident edge
In an undirected graph, we say that an edge is incident on a vertex if the vertex is an end point of the edge
what is out-degree
In a digraph, the number of edges coming out of a vertex is called out-degree of that vertex.
