0
Comparing the greedy approach alogorithm and the backtracking algorithm for the 0-1 knapsack problem with example?
Wiki User
ā 16y ago
1
Orval Kuphal
Wiki User
ā 11y ago#include
int x[12],w[12],pr[12],m,n,z,val;
void main()
{
int k,i;
float r=0;
void knapsack(float,int,float);
int s1=0;
clrscr();
printf("\n\n\t\tKNAPSACK PROBLEM USING BACKTRACKING\n\n");
printf("\n\tEnter the No. of Items : ");
scanf("%d",&n);
printf("\n\tEnter the Weight & Value for the Items \n");
for(i=0;i
printf("\n\titem %d : ",i+1);
scanf("%d%d",&w[k],&pr[k]);
r+=w[k];
s1+=pr[k];
}
printf("\n\n\t\tEnter the Knapsack Capacity : ");
scanf("%d",&m);
printf("\n\n\tITEMS IN THE KNAPSACK\n\n");
printf("\titem\tweight\tvalue\n\n");
knapsack(0,1,r);
getch();
}
void knapsack(float s,int k,float r)
{
int j,p;
x[k]=1;
if(s+w[k]==m)
{
printf("%d Set\n",++z);
for(j=1;j<=k;j++)
{
if(x[j])
{
printf("\n%d\t%d\t",j,w[j]);
printf("%d ",pr[j]);
}
}
printf("\n\n");
}
else if(s+w[k]+w[k+1]<=m)
knapsack(s+w[k],k+1,r-w[k]);
if((s+r-w[k]>=m) && (s+w[k+1]<=m))
{
x[k]=0;
knapsack(s,k+1,r-w[k]);
}
}
Wiki User
ā 16y ago1. divide & conquer 2. greedy method 3. dynamic programming 4. back tracking 5. branch & bound
Add your answer:
Earn +20 pts
What is the text-based approach to documenting an algorithm?
pseudocode
Which one is better kruhskal's algorithm or prim's algorithm?
Both algorithms have the same efficiency and both are based on the same greedy approach. But Kruskal's algorithm is much easier to implement.
Difference between boundary fill algorithm and scanline polygon fill algorithm?
in scan line polygon fill, each can line crossing a polygon, the area fill algorithm locates the intersection point of the scan line with the polygon edges. These intersection points are then stored from left to right and the corresponding frame buffer positions between each intersection painr are set to the specified fill color. In boundary fill, approach to area filling is to start at a point inside a region and paint the interior outward toward and the boundary.
How do you do th decryption of passwords encrypted by one way hashing algorithm?
You can't decrypt them, that's why it's called one-way. The only way to get the password is to encrypt guess words with the same algorithm and checking if the result matches the encrypted password. So if your encrypted password is a9d82da, guess what it might be - maybe "frank"? - and encrypt that word, and if you get 29d8afd, you know the password is not "frank", so try another word. If one of them encrypts into a9d82da, then you know that's the password.Passwords are often guessed this way by using a dictionary - a simple list of words - and automatically encrypting them one by one and comparing the result with the encrypted password. Another approach that takes much longer is to try every possible combination of characters, such as aa, ab, ac, aaa, aab, aac, aba, abb, abc, etc. This can take weeks, months, even years, depending on the algorithm used and the speed of your computer.
How does Prim's algorithm differ from Kruskal's and Dijkstra's algorithms?
First a vertex is selected arbitrarily. on each iteration we expand the tree by simply attaching to it the nearest vertex not in the tree. the algorithm stops after all yhe graph vertices have been included.. one main criteria is the tree should not be cyclic.
What is a text based approach to documenting an algorithm?
pseudocode
What is the text-based approach to documenting an algorithm?
pseudocode
Is a text based approach to documenting an algorithm?
pseudocode
Which data structures is suitable for implementing backtracking?
Backtracking is a general algorithmic technique for finding solutions to complex problems. It considers all possible solutions when trying to solve a complex problem. The general algorithm for backtracking is as follows: Backtracking_algorithm(Option X) If X is a solution to the given problem Add to solutions Backtracking_algorithm(Expand X) ELSE return 0 We begin the backtracking process by choosing one option. We return to the solution if the problem can be solved with that option. Otherwise, we go back and choose an alternative from the remaining options. Additionally, none of the options may help you find the solution, in that case, the algorithm returns nothing and going backwards won't help you find a solution to that specific issue. The data structures suitable for implementing backtracking are stacks, linked lists, matrices and graphs. You can understand the implementation of backtracking by visiting the following examples of backtracking applications: Finding Hamilton cycle in Graphs: Hamilton cycle is a closed loop or graph cycle visiting each node exactly once while traversing the graph. The backtracking technique makes it simple to locate every Hamiltonian Cycle that exists in the provided undirected or directed graph. Finding all of the Hamiltonian Paths in a graph is NP-complete. The goal is to traverse the network using the Depth-First Search algorithm until each vertex has been observed. During the traversal, we go back to look for other paths using backtracking. Maze-solving problem: Backtracking is also used to solve the maze problem. The algorithm is implemented using a matrix data structure. In a maze problem, a player begins at one location and moves through a sequence of obstacles to reach a specific destination. The rat maze issue is another name for this game. N Queen Problem: The N queen problem is another example of backtracking implementation using a matrix data structure. It is one of the famous backtracking problems. The N Queen problem deals with arranging N chess queens on an NāN chessboard without having them attack another queen. The sum of subset problem: Finding a subset of elements selected from a given collection whose sum equals a given number K is known as the subset sum problem. One can use a backtracking approach to solve the sum of the subset problem. You can use a tree data structure to implement backtracking in the sum of the subset problem. In this problem, the backtracking method attempts to choose a valid subset when an element is invalid. We return to get the previous subset and add another element to get the answer. Graph Colouring problem: The graph colouring problem aims to assign colours to specific graph elements while following certain guidelines and limitations. One can use the backtracking method to solve the colouring problem of a given graph. The approach is to traverse the graph and colour the node if the current node violates guidelines, backtrack and return false.
Which one is better kruhskal's algorithm or prim's algorithm?
Both algorithms have the same efficiency and both are based on the same greedy approach. But Kruskal's algorithm is much easier to implement.
What is stantard algorithm?
Algorithm means Step-by-Step procedure to acheive the required result in a meaningful manner. standard algorithm is one which not only concerate to get the required result but follows some systematic approach to get that result...
How is time complexity of an algorithm calculated?
The usual definition of an algorithm's time complexity is called Big O Notation. If an algorithm has a value of O(1), it is a fixed time algorithm, the best possible type of algorithm for speed. As you approach O(∞) (a.k.a. infinite loop), the algorithm takes progressively longer to complete (an algorithm of O(∞) would never complete).
What is back tracking in ai?
Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.[1][2][3]The classic textbook example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight queens on a standard chessboard so that no queen attacks any other. In the common backtracking approach, the partial candidates are arrangements ofk queens in the first k rows of the board, all in different rows and columns. Any partial solution that contains two mutually attacking queens can be abandoned, since it cannot possibly be completed to a valid solution.
What is the best approach to take in comparing policies for private health coverage?
The best approach to take when comparing policies for private health coverage, would be to find a few that you like and compare the prices of the ones you chose. See which ones include better coverage at a cost that fits your budget.
How do you implement algorithm in layered approach using conditional random field intrusion detection?
if u having this project means mail to aravindramesh11@gmail.com
Which is the site where you can get information about the jobs?
Its perfectly "Mydeals247" .Because when i approach with other sites i didn't get perfect information some times it may be fake also. but when i approach MyDeals247 i got right information with in a less time comparing other sites.
Difference between boundary fill algorithm and scanline polygon fill algorithm?
in scan line polygon fill, each can line crossing a polygon, the area fill algorithm locates the intersection point of the scan line with the polygon edges. These intersection points are then stored from left to right and the corresponding frame buffer positions between each intersection painr are set to the specified fill color. In boundary fill, approach to area filling is to start at a point inside a region and paint the interior outward toward and the boundary.
