This repository has been archived by the owner on Aug 23, 2023. It is now read-only.
/
BoxStacking.cs
122 lines (101 loc) · 3.56 KB
/
BoxStacking.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace CS.Problems.DynamicProgramming
{
/// <summary>
/// Problem statement below
/// http://www.geeksforgeeks.org/dynamic-programming-set-21-box-stacking-problem/
/// </summary>
public class BoxStacking
{
public static int GetMaxHeight(List<int[]> dimensions)
{
var allDims = new List<Box>();
//each box can be stacked in six differant ways (six sides)
foreach (var dim in dimensions)
{
allDims.Add(new Box(dim[0], dim[1], dim[2]));
allDims.Add(new Box(dim[2], dim[1], dim[0]));
allDims.Add(new Box(dim[1], dim[2], dim[0]));
allDims.Add(new Box(dim[0], dim[2], dim[1]));
allDims.Add(new Box(dim[2], dim[0], dim[1]));
allDims.Add(new Box(dim[1], dim[0], dim[2]));
}
//stable quick sort by decreasing order of Base Size
allDims = allDims.OrderByDescending(x => x).ToList();
var maxHeight = -1;
//now lets find the longest increasing sub seq
//with max height
FindMaxHeight(allDims, allDims.Count - 1, ref maxHeight, new Dictionary<int, int>());
return maxHeight;
}
/// <summary>
/// Return the longest height possible
/// from sequence such that box base size (0,1,..j-1) < box size j
/// </summary>
/// <param name="allDims"></param>
private static int FindMaxHeight(List<Box> input,
int j, ref int netMax, Dictionary<int, int> cache)
{
if (j == 0)
{
return input[0].Height;
}
if (cache.ContainsKey(j))
{
return cache[j];
}
var currentMax = input[j].Height;
for (int i = 0; i < j; i++)
{
var subMax = FindMaxHeight(input, i, ref netMax, cache);
//check for box size
//And if subMax of values from (0, 1, .., i) + value at j is better
if (input[i].Length > input[j].Length
&& input[i].Breadth > input[j].Breadth
&& input[j].Height + subMax > currentMax)
{
currentMax = input[j].Height + subMax;
}
}
netMax = Math.Max(netMax, currentMax);
cache.Add(j, currentMax);
return currentMax;
}
internal class Box : IComparable
{
public int Height { get; set; }
public int Breadth { get; set; }
public int Length { get; set; }
public Box(int height, int breadth, int length)
{
Height = height;
Breadth = breadth;
Length = length;
}
/// <summary>
/// Compare Box base size
/// </summary>
/// <param name="obj"></param>
/// <returns></returns>
public int CompareTo(object obj)
{
var box = obj as Box;
if (Breadth < box.Breadth
&& Length < box.Length)
{
return -1;
}
else if (Breadth == box.Breadth
&& Length == box.Length)
{
return 0;
}
return 1;
}
}
}
}