3
\$\begingroup\$

Is this code written in a decent style? Appreciate some feedback : )

private static int Max(int a, int b)
{
    return a > b ? a : b;
} 

/// <summary>
/// Returns the solution to Knapsack01 problem. Uses bottom up dynamic programming.
/// </summary>
private static int Knapsack01(int capacity, int[] values, int[] weights)
{
    int[,] table = new int[values.Length + 1, capacity + 1];


    for (int row = 0; row <= values.Length; row++)
    {
        for (int column = 0; column <= capacity; column++)
        {
            if (row == 0 || column == 0)
            {
                // base case
                table[row, column] = 0;
            }

            else if (weights[row -1] <= column)
            {
                // item fits 
                int valueAbove = table[row - 1, column];
                int spareCapacity = column - weights[row - 1];
                int currentValue = values[row - 1] + table[row - 1, spareCapacity];
                table[row, column] = Max(valueAbove, currentValue);
            }

            else
            {
                // item doesn't fit so copy value from above cell
                table[row, column] = table[row - 1, column];
            }
        }
    }

    return table[values.Length, capacity];
}
\$\endgroup\$
1
\$\begingroup\$

I might redefine Max() as

private static T Max<T>(T a, T b) where T : IComparable<T>
{
    return a?.CompareTo(b) > 0 ? a : b;
}

to be able to be reusable for any type that implements the IComparable<T> interface (int implements IComparable<int>, so it still works as expected). It'll be a tad slower, but it will quickly give you the max of just about anything, ints, doubles, strings...

\$\endgroup\$
  • \$\begingroup\$ What's the point? OP's entire code is built on the use of int types, not generic types. YAGNI, there's no reason to over-engineer this. \$\endgroup\$ – Flater Feb 9 '18 at 13:14
  • \$\begingroup\$ I hardly call 5-10 seconds of thought over-engineering, but to each their own. \$\endgroup\$ – Jesse C. Slicer Feb 9 '18 at 13:23
  • \$\begingroup\$ You're adding complexity for no discernible benefit. Quantifying the amount of complexity is irrelevant. There is no current (nor expected) use case for using other types. If anything, the entire method should be discarded as it's simply repeating the Math.Max() behavior (which already works for more than just ints). \$\endgroup\$ – Flater Feb 9 '18 at 14:49
1
\$\begingroup\$

It's not exactly well-documented. You can sort of determine what the "Knapsack problem" is by looking at a few comments and some variable names, but if I were the developer, I'd probably add a comment block to describe how it works in case someone else came upon this code later and needed to understand it quickly.

I'm not quite sure why they didn't just use Math.Max instead of creating their own function (maybe they ported it from some other language that didn't have that function handy?).

Aside from those things, if it's functional and returns accurate results, then I don't see a huge problem with it.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.