Knapsack Problem Algoritham in C#

In this article, we will see C# implementation for the Knapsack problem 

The Knapsack Problem is a famous Dynamic Programming Problem that falls in the optimization category.

 It derives its name from a scenario where, given a set of items with specific weights and assigned values, the goal is to maximize the value in a knapsack while remaining within the weight constraint. 

Each item can only be selected once, as we don’t have multiple quantities of any item.

Example

Let’s take the example of Mary, who wants to carry some fruits in her knapsack and maximize the profit she makes. She should pick them such that she minimizes weight ( $<= bag's$ $capacity$) and maximizes value.

Here are the weights and profits associated with the different fruits:

Items: { Apple, Orange, Banana, Melon }

Weights: { 2, 3, 1, 4 }

Profits: { 4, 5, 3, 7 }

Knapsack Capacity: 5

Fruits Picked by Mary:

Banana + Melon

💰Profit = 10

Banana and Melon is the best combination, as it gives us the maximum profit (10) and the total weight does not exceed the knapsack’s capacity (5).

Basic Solution

The problem can be tackled using various approaches: brute force, top-down with memoization, and bottom-up are all potentially viable approaches to take.

The latter two approaches (top-down with memoization and bottom-up) make use of Dynamic Programming. In more complex situations, these would likely be the much more efficient approaches to use.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace CsharpAlgorithm {

  class CsharpAlgo {

    static void Main(string[] args) {

      int[] Weights = { 2, 3, 1, 4 };

      int[] Profits = { 4, 5, 3, 7 };

            int capacity = 5;

            int itemsCount = 4;

            int result = KnapSackAlgo(capacity, Weights, Profits, itemsCount);

      Console.WriteLine(result);

    }

    public static int KnapSackAlgo(int capacity, int[] weight, int[] value, int count) {

      int[,] K = new int[count + 1, capacity + 1];

      for (int i = 0; i <= count; ++i)

      {

        for (int w = 0; w <= capacity; ++w)

        {

          if (i == 0 || w == 0)

            K[i, w] = 0;

          else if (weight[i - 1] <= w)

            K[i, w] = Math.Max(value[i - 1] + K[i - 1, w - weight[i - 1]], K[i - 1, w]);

          else

            K[i, w] = K[i - 1, w];

        }

      }

      return K[count, capacity];

    }

  }

}

 

Cop

--------------------------------------------

Author : Dotnet Office | https://www.youtube.com/TheDotNetOffice

Share this

Related Posts