Showing posts with label C# Tutorials. Show all posts
Showing posts with label C# Tutorials. Show all posts

Rod Cutting Problem in C#

 The rod-cutting problem is the classic dynamic programming problem. In this problem, we cut a rod of a given length into smaller pieces with certain prices for each piece.

As per this problem, we need to determine the maximum revenue profit that can be get by cutting up the rod and selling the pieces of rod.

Problem statement:

 

Given a rod of length n and we need to cut the rod in such a way that we need to sell it for the maximum revenue profit. We also have the price table, which tells us the worth of the rod.

Length =

1

2

3

4

5

Price   =

1

5

6

9

10

 

 

So, according to the above table, if we cut the rod of length 1 we can sell it for $1.

Similarly, if we cut the rod at length 2, we can sell it at $5 and if we cut the rod at length 3, we can sell it at $6.

According to the problem, we need to find a way, how to cut the rod so that we can get maximum profit.

Here rod length is 5, so if we give the whole rod, without cutting it so the profit is $10. But if we cut the rod at length 2 and at length 3 (so total rod size is 2+3 = 5), then the total profit will be 5 + 6 = 11. This gives us maximum profit.

Dynamic programming solution

static void Main(string[] args)

{

 

int[] price = new int[] { 1, 5, 6, 9, 10 };

int length = price.Length;

Console.WriteLine("Total Profit is :- " + Class1.TotalProfitToCutRod(price, length));

 

}

 

        public static int TotalProfitToCutRod(int[] p, int n)

        {

            int[] r = new int[n + 1];

            r[0] = 0;

 

            for (int j = 1; j <= n; j++)

            {

                int q = int.MinValue;

                for (int i = 1; i <= j; i++)

                {

                    q = Math.Max(q, p[i - 1] + r[j - i]);

                }

                r[j] = q;

            }

            return r[n];

        }

 

In this implementation, p is the array of prices for each piece length of rod and n is the length of the rod. This function returns the maximum profit that we get by cutting up the rod.

Naive recursive solution

static void Main(string[] args)

{

 

int[] price = new int[] { 1, 5, 6, 9, 10 };

int length = price.Length;

Console.WriteLine("Total Profit is :- " + Class1.TotalProfitToCutRod(price, length));

 

}

 

  public static int TotalProfitToCutRod(int[] p, int n)

        {

            if (n <= 0)

                return 0;

            int maximum_val = int.MinValue;

 

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

                maximum_val = Math.Max(maximum_val, p[i] +   TotalProfitToCutRod(p, n - i - 1));

 

            return maximum_val;

        }

 



 

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

Find total number of ways to reach the n’th stair from the bottom in C#

  In this article, we will see how to find total ways to reach the n’th stair from the bottom in C#

Given a staircase, where we need to find the total number of ways to reach to the n'th stair from the bottom of the staircase.

A person can only climb either the 1 or 2 stairs at a time. 

To understand it let's take an example,

The total number of ways to reach the 4th stair is 5,
 
1 step + 1 step + 1 step + 1 step
2 steps + 1 step + 1 steps
1 step + 1 steps + 2 steps
1 step + 2 steps + 1 steps
2 steps + 2 steps

Problem

Let's understand T(n) is the total number of ways to reach the n'th stair from the bottom form staircase. Since a person is only allowed to climb either 1 or 2 stairs at a time, so the person can reach the n'th stair from either the (n-1)'th stair, (n-2)'th stair.

Considering this is the recurrence relation T(n) , can be written as:

T(n) = T(n-1) + T(n-2) , where n >= 0 and the
T(0) = 1, T(1) = 1

Problem-solving 

There are many ways to perform to count the number of ways to reach the nth stair in C#.

One common way to is the Bottom-up/ dynamic approach and another is the Top-up/Recursive approach.

Bottom-Up Approach/ dynamic approach

The bottom-up approach uses dynamic programming, where it starts by calculating the number of ways to reach the first few staircases (in this case, the first two stairs) and then uses these values to calculate the number of ways to reach higher stairs.

static void Main(string[] args) {
    Console.WriteLine("give number of stairs to reach");
    int number = Convert.ToInt16(Console.ReadLine());
    Console.WriteLine("Number of ways to reach:- " + Class1.CountStairWays(number));
}
public static int CountStairWays(int stairNumber) {
    if (stairNumber <= 0) {
        return 0;
    } else if (stairNumber == 1) {
        return 1;
    } else if (stairNumber == 2) {
        return 2;
    }
    int[] stairArray = new int[stairNumber + 1];
    stairArray[0] = 0;
    stairArray[1] = 1;
    stairArray[2] = 2;
    for (int i = 3; i <= stairNumber; i++) {
        stairArray[i] = stairArray[i - 1] + stairArray[i - 2];
    }
    return stairArray[stairNumber];
}
C#

The time complexity of the above solution is O(n), where n is the size of the input, And The space complexity of the above solution is O(n).

Top-up approach/ recursive function and memorization

This function uses the top-down approach, where it starts by trying to find the number of ways to reach the nth stair by breaking the problem down into smaller sub-problems (in this case, finding the number of ways to reach the n-1th and n-2nd stairs) and then combining the solutions to these subproblems to find the solution to the original problem.

Note that the above examples uses the Fibonacci sequence, where each number is the sum of the two preceding ones, starting from 0 and 1.

static void Main(string[] args) {
    Console.WriteLine("give number of stairs to reach");
    int number = Convert.ToInt16(Console.ReadLine());
    int[] stairArray = new int[number + 1];
    Console.WriteLine("Number of ways to reach:- " + Class1.CountStairWaysUsingRecursive(number, stairArray));
}
public static int CountStairWaysUsingRecursive(int stairNumber, int[] stairArray) {
    if (stairNumber <= 0) {
        return 0;
    } else if (stairNumber == 1) {
        return 1;
    } else if (stairNumber == 2) {
        return 2;
    }
    if (stairArray[stairNumber] == 0) {
        stairArray[stairNumber] = CountStairWaysUsingRecursive(stairNumber - 1, stairArray) + CountStairWaysUsingRecursive(stairNumber - 2, stairArray);
    }
    return stairArray[stairNumber];
}
C#

Output





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

Find out all unique combinations of sum of a Number N in C#

 In this article, we will see how to find the unique combination of the sum from the given number in C#.

1. Combination Sum – Problem Statement

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to the target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to the target is less than 150 combinations for the given input.

Example 1:


Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:


Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:


Input: candidates = [2], target = 1
Output: []

Example 4:


Input: candidates = [1], target = 1
Output: [[1]]

Example 5:


Input: candidates = [1], target = 2
Output: [[1,1]]


C# Code:

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace ConsoleApplication1
{
    public class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Please give number to get sum");
            int num = Convert.ToInt16(Console.ReadLine());
            UniqueNumberTobeSum(num);
        }

        public static void UniqueNumberTobeSum(int num)
        {
            int[] array = new int[num + 1];
            for (int i = 1; i <= num; i++)
            {
                array[i] = i;
            }
            List<int> currentList = new List<int>();
            List<List<int>> output = new List<List<int>>();
            UniqueCombinationSum(array, num, 0, 1, currentList, output);
            Console.WriteLine("unique combinations of sum of a Number ");
            foreach (var item in output)
            {
                StringBuilder s = new StringBuilder();
                foreach (var item1 in item)
                {
                    s.Append(item1.ToString());
                }

               
                Console.WriteLine(s);
                s = null;
            }
        }
        private static void UniqueCombinationSum(int[] array, int target, int sum, int index, List<int> currentList, List<List<int>> output)
        {
            if (sum == target)
            {
                List<int> newList = new List<int>();
                newList.AddRange(currentList);
                output.Add(newList);
                return;
            }
            else if (sum > target)
            {
                return;
            }
            else
            {
                for (int i = index; i < array.Length; i++)
                {
                    currentList.Add(array[i]);
                    UniqueCombinationSum(array, target, sum + array[i], i + 1, currentList, output);
                    currentList.Remove(array[i]);
                }
            }
        }

    }


}

Output:






If the number is 6 then the output is below



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