Knapsack with floating point capacity uses only small items

[Swahhillie]

Description

The knapsack algorithm breaks if it can't fill the whole bag.
It will fill the entire bag with the smallest weight item instead.

Version

• Unity: 2019.4.35f
• ProceduralToolkit: 0.2.3

Steps to reproduce

public void TestKnapsack()
{
    var set = new Dictionary<int, float>()
    {
        { 1, 1f }, { 2, 2f }, { 4, 4f }
    };
    
    string Result(Dictionary<int, int> result)
    {
        var str = "";
        foreach (var p in result)
        {
            str += $"{p.Key} * {p.Value}\n";
        }

        return str;
    }

    var ten = PTUtils.Knapsack(set, 10.0f);
    var tenPointFive = PTUtils.Knapsack(set, 10.5f);
    
    //as expected
    Debug.Log(Result(ten));
    //4 * 2
    //2 * 1
    //1 * 0
    
    //wrong
    Debug.Log(Result(tenPointFive));
    //4 * 0
    //2 * 0
    //1 * 10
}

Run the provided code and see that the result is not as expected.

[BasmanovDaniil]

Nice catch, thanks, I will take a look!

[BasmanovDaniil]

@Swahhillie, I've changed the behaviour to be more consistent with expectations, you can see the new version here:

ProceduralToolkit/Runtime/PTUtils.cs

Lines 61 to 159 in 48c93f9

	/// <summary>
	/// Knapsack problem solver for items with equal value
	/// </summary>
	/// <typeparam name="T">Item identificator</typeparam>
	/// <param name="set">Set of items where key <typeparamref name="T"/> is item identificator and value is item weight</param>
	/// <param name="capacity">Maximum weight</param>
	/// <param name="knapsack">Pre-filled knapsack</param>
	/// <param name="overloadKnapsack">Set to true if you want to fill the remaining free space with the smallest item</param>
	/// <returns>
	/// Filled knapsack where values are number of items of type key.
	/// <remarks>
	/// https://en.wikipedia.org/wiki/Knapsack_problem
	/// </remarks>
	public static Dictionary<T, int> Knapsack<T>(Dictionary<T, float> set, float capacity,
	Dictionary<T, int> knapsack = null, bool overloadKnapsack = false)
	{
	var keys = new List<T>(set.Keys);
	// Sort keys by their weights in descending order
	keys.Sort((a, b) => -set[a].CompareTo(set[b]));
	if (knapsack == null)
	{
	knapsack = new Dictionary<T, int>();
	foreach (var key in keys)
	{
	knapsack[key] = 0;
	}
	}
	return Knapsack(set, keys, capacity, knapsack, 0, overloadKnapsack);
	}
	private static Dictionary<T, int> Knapsack<T>(Dictionary<T, float> set, List<T> keys, float remainder,
	Dictionary<T, int> knapsack, int startIndex, bool overloadKnapsack)
	{
	T smallestKey = keys[keys.Count - 1];
	if (remainder < set[smallestKey])
	{
	if (overloadKnapsack)
	{
	knapsack[smallestKey] = 1;
	}
	return knapsack;
	}
	// Cycle through items and try to put them in knapsack
	for (var i = startIndex; i < keys.Count; i++)
	{
	T key = keys[i];
	float weight = set[key];
	// Larger items won't fit, smaller items will fill as much space as they can
	knapsack[key] += (int) (remainder/weight);
	remainder %= weight;
	}
	if (remainder > 0)
	{
	if (overloadKnapsack)
	{
	knapsack[smallestKey] += 1;
	remainder -= set[smallestKey];
	}
	// Fix for https://github.com/Syomus/ProceduralToolkit/issues/72
	var repackedCopy = new Dictionary<T, int>(knapsack);
	// Throw out largest item and try again
	for (var i = 0; i < keys.Count; i++)
	{
	T key = keys[i];
	if (repackedCopy[key] != 0)
	{
	// Already tried every combination, return as is
	if (key.Equals(smallestKey))
	{
	return repackedCopy;
	}
	repackedCopy[key]--;
	remainder += set[key];
	startIndex = i + 1;
	break;
	}
	}
	repackedCopy = Knapsack(set, keys, remainder, repackedCopy, startIndex, overloadKnapsack);
	if (TotalWeight(set, repackedCopy) > TotalWeight(set, knapsack))
	{
	knapsack = repackedCopy;
	}
	}
	return knapsack;
	}
	private static float TotalWeight<T>(Dictionary<T, float> set, Dictionary<T, int> knapsack)
	{
	float weight = 0;
	foreach(var item in knapsack)
	{
	weight += set[item.Key] * item.Value;
	}
	return weight;
	}