0-1 Knapsack Problem in C Using Dynamic Programming

Here you will learn about 0-1 knapsack problem in C.

We are given n items with some weights and corresponding values and a knapsack of capacity W. The items should be placed in the knapsack in such a way that the total value is maximum and total weight should be less than knapsack capacity.

In this problem 0-1 means that we can’t put the items in fraction. Either put the complete item or ignore it. Below is the solution for this problem in C using dynamic programming.

Knapsack Problem in C Using Dynamic Programming
Program for Knapsack Problem in C Using Dynamic Programming

 

Output

Enter number of items:3
Enter value and weight of items:
100 20
50 10
150 30
Enter size of knapsack:50
250

 

You can watch below video to learn knapsack problem easily.

Source: http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/

Category: DSA

Leave a Reply

Your email address will not be published. Required fields are marked *