6
\$\begingroup\$

This is my version of the knapsack challenge and I was wondering if there was a way to do it so it doesn't go through the foreach statement so many times. At the minute it goes through it thousands of times to get he closes value to the target number, which takes long time to do, I was wondering if there was a way to either do it without foreach or make it quick with the foreach.

private void btnGenerate_Click(object sender, RoutedEventArgs e)
{
    string input;
    string bag;
    int goal;
    int count = 0;

    int element;
    List<int> finalResult = new List<int>();
    do
    {
        bag = txtBag.Text;
    }
    while (!int.TryParse(bag, out goal));
    input = txtGenerate.Text;
    string[] elementsText = input.Split(' ');
    List<int> elementsList = new List<int>();
    foreach (string elementText in elementsText)
    {

        if (int.TryParse(elementText, out element))
        {
            elementsList.Add(element);
        }
    }
    Solver solver = new Solver();
    List<List<int>> results = solver.Solve(goal, elementsList.ToArray());
    int closestValue = 0;
    foreach (List<int> result in results)
    {
        count++;
        int totalValue = result.Sum(x => Convert.ToInt32(x));

        if (totalValue >= closestValue)
        {
            closestValue = totalValue;
            finalResult = result;
            txtSum.Text = closestValue.ToString();

        }
    }

    foreach (int value in finalResult)
    {
        txtCount.Text = count.ToString();

        cboResult.ItemsSource = finalResult;

    }
}

I also have a class with this in:

public class Solver
{
    public List<List<int>> mResults;
    public int closestValue = 0;
    public List<List<int>> Solve(int goal, int[] elements)
    {
        mResults = new List<List<int>>();
        RecursiveSolve(goal, 0, new List<int>(), new List<int>(elements), 0);
        return mResults;
    }

    private void RecursiveSolve(int goal, int currentSum,
    List<int> included, List<int> notIncluded, int startIndex)
    {
        for (int index = startIndex; index < notIncluded.Count; index++)
        {
            int nextValue = notIncluded[index];
            if (currentSum + nextValue <= goal && currentSum + nextValue >= closestValue)
            {
                List<int> newResult = new List<int>(included);
                newResult.Add(nextValue);
                mResults.Add(newResult);
                closestValue = currentSum + nextValue;
            }
            if (currentSum + nextValue < goal)
            {

                List<int> nextIncluded = new List<int>(included);
                nextIncluded.Add(nextValue);
                List<int> nextNotIncluded = new List<int>(notIncluded);
                nextNotIncluded.Remove(nextValue);
                RecursiveSolve(goal, currentSum + nextValue,
                    nextIncluded, nextNotIncluded, startIndex++);
            }
        }
    }
}
\$\endgroup\$
3
\$\begingroup\$

You've got logic mixed in with your view.

Move as much of the code out of your button handler as you can, and into a separate function (and preferably a separate class).

A button handler should do just that, handle button presses. It should not then perform calculations.


Your spacing could use some work. For example:

    int element;
    List<int> finalResult = new List<int>();
    do
    {
        bag = txtBag.Text;
    }
    while (!int.TryParse(bag, out goal));
    input = txtGenerate.Text;
    string[] elementsText = input.Split(' ');
    List<int> elementsList = new List<int>();
    foreach (string elementText in elementsText)
    {

        if (int.TryParse(elementText, out element))
        {
            elementsList.Add(element);
        }
    }
    Solver solver = new Solver();
    List<List<int>> results = solver.Solve(goal, elementsList.ToArray());
    int closestValue = 0;
    foreach (List<int> result in results)
    {
        count++;
        int totalValue = result.Sum(x => Convert.ToInt32(x));

        if (totalValue >= closestValue)
        {
            closestValue = totalValue;
            finalResult = result;
            txtSum.Text = closestValue.ToString();

        }
    }

Would be a lot more readable like this:

    int element;
    List<int> finalResult = new List<int>();

    do
    {
        bag = txtBag.Text;
    }
    while (!int.TryParse(bag, out goal));

    input = txtGenerate.Text;
    string[] elementsText = input.Split(' ');
    List<int> elementsList = new List<int>();

    foreach (string elementText in elementsText)
    {

        if (int.TryParse(elementText, out element))
        {
            elementsList.Add(element);
        }
    }

    Solver solver = new Solver();
    List<List<int>> results = solver.Solve(goal, elementsList.ToArray());
    int closestValue = 0;

    foreach (List<int> result in results)
    {
        count++;
        int totalValue = result.Sum(x => Convert.ToInt32(x));

        if (totalValue >= closestValue)
        {
            closestValue = totalValue;
            finalResult = result;
            txtSum.Text = closestValue.ToString();

        }
    }

Use var when it is obvious from the RHS of a declaration what the type of the variable is, and always use var in foreach loops.

e.g.

    int element;
    var finalResult = new List<int>();

    do
    {
        bag = txtBag.Text;
    }
    while (!int.TryParse(bag, out goal));

    input = txtGenerate.Text;
    var elementsText = input.Split(' ');
    var elementsList = new List<int>();

    foreach (var elementText in elementsText)
    {

        if (int.TryParse(elementText, out element))
        {
            elementsList.Add(element);
        }
    }

    var solver = new Solver();
    List<List<int>> results = solver.Solve(goal, elementsList.ToArray());
    var closestValue = 0;

    foreach (var result in results)
    {
        count++;
        int totalValue = result.Sum(x => Convert.ToInt32(x));

        if (totalValue >= closestValue)
        {
            closestValue = totalValue;
            finalResult = result;
            txtSum.Text = closestValue.ToString();
        }
    }

Avoid Hungarian notation in C#, and prefer public properties over public fields. Additionally, public collections should be readonly, and you don't need to intiialize an integer as 0. Its default value is 0.

    private readonly List<List<int>> results

    public List<List<int>> Results 
    {
        get 
        {
            return results;
        }
    }

    public int ClosestValue {get; set;}
\$\endgroup\$
  • 1
    \$\begingroup\$ "prefer public properties over public fields" Yes, but also prefer private fields over both. I don't see any reason why those should be public here. \$\endgroup\$ – svick Oct 10 '14 at 11:52
  • \$\begingroup\$ Very good point. \$\endgroup\$ – Nick Udell Oct 10 '14 at 12:01
3
\$\begingroup\$

WPF is not WinForms. You should look into how binding works in WPF and into the MVVM pattern.


string input;
string bag;
int goal;
int count = 0;

You shouldn't declare your variables at the start of the method like this. Declare them when you need them.


do
{
    bag = txtBag.Text;
}
while (!int.TryParse(bag, out goal));

If I understand this code correctly, If txtBag contains a valid int, it will set its value to the goal variable, otherwise it will loop forever. That might be okay if you're writing a Turing machine, but not if you're writing a real program. If the goal was to give the user a chance to fix incorrect input, then this code doesn't achieve it.


if (int.TryParse(elementText, out element))
{
    elementsList.Add(element);
}

In production code, invalid input should cause an error, not be silently ignored.


List<List<int>> results = solver.Solve(goal, elementsList.ToArray());

Why does Solver return some (?!) valid combinations and not just the best one?


count++;

Why are you computing this, when you could just use results.Count?


result.Sum(x => Convert.ToInt32(x))

result is already a collection of ints, there is no need for a conversion.


To find the maximum value, you need to iterate over all the values. But you can at least simplify your code by using MaxBy() from MoreLINQ.


With the suggestions above, this part of your code could look like this:

if (results.Any())
{
    var closest = results
        .Select(result => new { result, totalValue = result.Sum() })
        .MaxBy(x => x.totalValue);

    closestValue = closest.totalValue;
    finalResult = closest.result;
    txtSum.Text = closestValue.ToString();
}

foreach (int value in finalResult)
{
    txtCount.Text = count.ToString();

    cboResult.ItemsSource = finalResult;
}

There is no reason for this to be a loop.


public class Solver
public List<List<int>> Solve(int goal, int[] elements)

Those are not very good names, they don't say anything about what are they actually solving.


elementsList is a List, that's converted to array using ToArray() (a copy) and then back to List inside Solve() using new List (another copy), that's unnecessary.


The way you're working with included and notIncluded means you're creating lots of copies. You might want to consider using one of the immutable collections.

\$\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.