Finding minimum length of tape required.

30 - 20 + 1 = 11
80 - 75 + 1 =  6
----------------
sum:          17

Quote:

let say if there are 150 cabins and 6 broken cabins 20, 30, 75, 80, 110, 140 and number of pieces to be cut is 3

.....20.....30....75....80.....110....140....
then
-----|-- 11 --|---|-- 6 --|-----|--31--|-----
or
-----|-- 11 --|---|----- 36 -----|---|-1-|---

now the answer is 11+6+31
but another possible ways is <code">56+31+1

1) 6 = 1 + 1 + 4 => 20, 30, {75, 80, 110, 140} => 1+1+66=68
2) 6 = 1 + 2 + 3 => 20, {30, 75}, {80, 110, 140} => 1+46+61=108
3) 6 = 1 + 3 + 2 => 20, {30, 75, 80}, {110, 140} => 1+51+31=83
4) 6 = 1 + 4 + 1 => 20, {30, 75, 80, 110}, 140 => 1+81+1=82
5) 6 = 2 + 1 + 3 => {20, 30}, 75, {80, 110, 140} => 11+1+61=73
6) 6 = 2 + 2 + 2 => {20, 30}, {75, 80}, {110, 140} => 11+6+31=48
7) 6 = 2 + 3 + 1 => {20, 30}, {75, 80, 110}, 140 => 11+36+1=48
8) 6 = 3 + 1 + 2 => {20, 30, 75}, 80, {110, 140} => 56+1+31=88
9) 6 = 3 + 2 + 1 => {20, 30, 75}, {80, 110}, 140 => 56+31+1=88
10) 6 = 4 + 1 + 1 => {20, 30, 75, 80}, 110, 140 => 56+1+1=58

Quote:

I tried in many different ways by taking gaps between the broken cabins and by sorting them

Quote:

I tried in many different ways by taking gaps between the broken cabins

Quote:

but some cases are not getting solve

//https://www.codeproject.com/Questions/5294427/Finding-minimum-length-of-tape-required

void Main()
{
	//broken cabins
	List<int> bc = new List<int>(){20, 30, 75, 80, 110, 140};
	//get all digits which sum is equal to number of broken cabins
	//in this case 6 - from {1,1,4}, {1, 2, 3}, ... {2, 2, 2} up to {4, 1, 1}
	int[,] comb = FactorizeUpToSum(6,3);
	//get dimension of an array
	int dmn = comb.Rank;
	//create a list of integers, to store all available sums
	List<int> allSums = new List<int>();
	//loop through the items in array
	for(int i=comb.GetLowerBound(0); i<comb.GetUpperBound(0); i++)
	{
		//length of tape used to cover broken cabins
		int sum = 0;
		//helper variable
		int k = 0;
		//loop through the items in a 'row'
		for(int j=0; j<=dmn; j++)
		{
			//calculate the distance between numbers
			sum += GetDistance(bc.Skip(k).Take(comb[i,j]));
			//increase number of "rows" to skip next time
			k+=comb[i,j];
		}
		//add sum onto the list
		allSums.Add(sum);
	}
	//get minimum length of tape
	int minSum = allSums.Min();
	Console.WriteLine($"Minimum length of tape necessary to cover {bc.Count} cabins in {dmn+1} pieces is {minSum} m.");
}



/// <summary>
/// returns a set of numbers which sum is egual to ...
/// for example: if [6] have to be a set of [3] numbers then 
/// below function returns {1,1,4}, {1,2,3}, {1,3,2}, ... {2,2,2}, up to {4,1,1}
/// </summary>
public int[,] FactorizeUpToSum(int sum, int cnt)
{
	int iniVal = Convert.ToInt32(new string('1', cnt)); //111
	int finVal = Convert.ToInt32(new string(Convert.ToChar($"{sum}"), cnt)); //666
	//calculate the lower bound of an array
	int upar = Combinations(sum, cnt)-Combinations(sum-1, cnt);
	int[,] items = new int[upar, cnt]; //create an array
	int i = 0;
	//loop through the numbers 111 to 666
	for(int curVal=iniVal; curVal<=finVal; curVal++)
	{
		//split number into an array of digits: 111 => {1,1,1}; 112 => {1,1,2} and so on...
		int[] tmp = curVal.ToString().Select(x=> ((int)x)-48).ToArray();
		if(tmp.Sum(x=>x)==sum && tmp.All(x=>x!=0))
		{
			for(int j=0; j<cnt; j++)
				items[i, j] = tmp[j];
			i++;
		}
	}
	return items;
}

public int Combinations(int cntGroup, int cntSets)
{
	return Factorial(cntGroup)/(Factorial(cntSets)*Factorial(cntGroup-cntSets));
}

public int Factorial(int nu)
{
	int f = 1;
	for(int i=1; i<=nu; i++)
		f*=i;
	return f;
}

/// <summary>
/// returs distance between numbers
/// </summary>
public int GetDistance(object o)
{
	int[] arr = ((IEnumerable)o).Cast<object>()
                 .Select(x => (int)x)
                 .ToArray();
	if(arr.Length>1)
		return (int)arr[arr.Length-1] - (int)arr[0] + 1;
	else
		return 1;
}

public static int minTape(int numBrokenCabins, int totalCabins, int numTapeCuts, int[] brokenCabins){
	    int firstCabin = brokenCabins[0];
	    int maxLength =  brokenCabins[brokenCabins.length-1] - firstCabin + 1;
	    int minLength = maxLength;
	    
	    // Base cases
        if(numTapeCuts == 1){
            return maxLength;
        }
        if(numTapeCuts == numBrokenCabins){
            return numBrokenCabins;
        }
        
        for(int i = 0; i < brokenCabins.length-1; i++){
            int currentCabin = brokenCabins[i];
            int thisLength = currentCabin - firstCabin + 1;
            int newNumBrokenCabins = numBrokenCabins - i - 1;
            int newTotalCabins = totalCabins;
            int newNumTapeCuts = numTapeCuts - 1;
            int[] newBrokenCabins = Arrays.copyOfRange(brokenCabins, i+1, brokenCabins.length);
            if(newNumBrokenCabins < newNumTapeCuts){
                break;
            }
            int totalLength = thisLength + minTape(newNumBrokenCabins, newTotalCabins, newNumTapeCuts, newBrokenCabins);
            minLength = totalLength < minLength ? totalLength : minLength;
        }
        
        return minLength;
	}