A programming problem similar to the knapsack problem

Question

I have asked about this on some stackexchange sites and they told me I should ask here with code provided, so here it is:

The whole problem is like knapsack problem but extended.

There is a knapsack with:

• weight,

• durability,

• max progress,

• max quality.

There are items. Each item has: weight, durability loss or gain, value that contributes to progress, value that contributes to quality.

There are also items that sort of add 'buffs' which:

• increase value that contributes to knapsack's progress and/or quality for next n items,

• reduce durability loss for next n items,

• add durability after picking next n items.

• n depends on buff.

Knapsack starts with weight, durability, 0 progress, 0 quality. Same items can be picked any number of times.

While picking items:

• knapsack gains weight,

• Knapsack gains progress,

• Knapsack gains quality,

• Knapsack loses or gains durability.

Same items can be picked any number of times.

You stop picking items if: Knapsack durability reaches 0, Knapsack progress reaches maximum progress, Knapsack cannot hold any item due to its weight.

Goal is to reach max quality and max progress with least amount of items and weight (if you reach max quality and max progress, it means you have solved the problem).

There are about 20 items so brute force will not work.

Code provided:

int maxWeight = 10;
int durability = 60;
int maxProgress = 100;
int maxQuality = 100;

int[] itemWeights =     new[] { 1,  1, 2,  3,   1,  1  };
int[] itemDurability =  new[] { 10, 0, 20, -15, 10, 10 };
int[] itemProgress =    new[] { 20, 0, 40, 0,   0,  0  };
int[] itemQuality =     new[] { 0,  0, 25, 0,   0,  0  };
int[] buffs =           new[] { 0,  1, 0,  0,   2,  3  };

//buff 1: for 4 next items after picking increase knapsack durability by 5
//buff 2: for 2 next items after picking increase progress gain by 50%
//buff 2: for 2 next items after picking increase quality gain by 50%

This is just an example code to make things simple. Real program includes over 20 actions, progress and quality depends on other variables and whole project is quite large and would probably make things complicated. However, if you need the whole source code it can be provided.

What I have tried: Using Genetic Algorithm to find most optimal solution and it worked but I want a mathematical solution. Using Dynamic Programming, solving quality actions first then continuing on progress. Things get complicated with items that add 'buff', since they do not have actual value.

Brute force attempt from actual project:

private void SolveForCurrentItems(Items[] availableItems, Items[] items)
        {
            Knapsack.RemoveItems();
            Knapsack.AddItems(items);
            var currentItems = Knapsack.GetItems();
            //Knapsack.GetItems() returns items that are used
            //if picking is no longer possible, last item is not included
            if (currentItems.Length == items.Length)
            {
                for (int i = 0; i < availableItems.Length; i++)
                {
                    var newItems = new Item[currentItems.Length + 1];
                    currentItems .CopyTo(newItems , 0);
                    newItems [newItems .Length - 1] = availableItems[i];
                    SolveForCurrentItems(availableItems, newItems);
                }
            }
        }

This loops through all possible solutions but it takes a lot of time. Note: Knapsack.AddItems(items) adds items and calculates all variables (weight, progress, quality, durability) and if some action fails, it is removed.

I minimized project:

Knapsack class:

 public class Knapsack
{
    public int MaxWeight { get; set; }
    public int Durability { get; set; }
    public int MaxProgress { get; set; }
    public int MaxQuality { get; set; }

    public int CurrentWeight { get; set; }
    public int CurrentDurability { get; set; }
    public int CurrentProgress { get; set; }
    public int CurrentQuality { get; set; }

    public double ProgressModifier { get; set; }
    public double QualityModifier { get; set; }
    public double DurabilityModifier { get; set; }
    public bool RestoreDurability { get; set; }


    public List<Item> CurrentItems { get; private set; }
    public List<Buff> CurrentBuffs { get; private set; }


    public Knapsack()
    {
        CurrentItems = new List<Item>();
        CurrentBuffs = new List<Buff>();
    }

    public void ExecuteItems()
    {
        CurrentWeight = 0;
        CurrentProgress = 0;
        CurrentQuality = 0;
        CurrentDurability = Durability;
        CurrentBuffs.Clear();
        ProgressModifier = 1;
        QualityModifier = 1;
        DurabilityModifier = 1;
        RestoreDurability = false;

        for (int i = 0; i < CurrentItems.Count; i++)
        {
            Item item = CurrentItems[i];

            // check if adding item is possible
            bool canAddItem = true;

            if (item.Weight + CurrentWeight > MaxWeight)
                canAddItem = false;

            if (CurrentProgress >= MaxProgress)
                canAddItem = false;

            if (CurrentDurability <= 0)
                canAddItem = false;

            if (!canAddItem)
            {
                //this item and the next ones are redundant
                CurrentItems.RemoveRange(i, CurrentItems.Count - i);
                return;
            }
            CurrentWeight += item.Weight;
            CurrentProgress += (int)(item.Progress * ProgressModifier);
            CurrentQuality += (int)(item.Quality * QualityModifier);
            if (item.Durability < 0)
                CurrentDurability -= item.Durability; //durability restoration
            else
                CurrentDurability -= (int)(item.Durability * DurabilityModifier); //durability loss

            if (CurrentDurability > 0 && RestoreDurability)
                CurrentDurability += 5; //if durability doesnt reach 0, you can add durability with restoration


            if (CurrentDurability > Durability)
                CurrentDurability = Durability; //current durability cannot exceed knapsacks durability


            foreach (var buff in CurrentBuffs)
                buff.Step(this);

            for (int j = 0; j < CurrentBuffs.Count; j++)
            {
                var buff = CurrentBuffs[j];
                if (buff.NeedsRemove)
                {
                    switch (buff.BuffType)
                    {
                        case BuffType.DurabilityRestoration:
                            RestoreDurability = false;
                            break;

                        case BuffType.DurabilityModifier:
                            DurabilityModifier = 1;
                            break;

                        case BuffType.Progress:
                            ProgressModifier = 1;
                            break;

                        case BuffType.Quality:
                            QualityModifier = 1;
                            break;
                    }
                    CurrentBuffs.Remove(buff);
                    j--;
                }
            }

            if (item.HasBuff)
            {
                //check if such buff exists
                var buff = CurrentBuffs.FirstOrDefault(x => x.BuffType == item.Buff.BuffType);
                if (buff == null) {
                    buff = item.Buff;
                    CurrentBuffs.Add(buff);
                }
                // reset stack of buff
                switch (buff.BuffType)
                {
                    case BuffType.DurabilityRestoration:
                        buff.CurrentStack = 4;
                        RestoreDurability = true;
                        break;

                    case BuffType.DurabilityModifier:
                        buff.CurrentStack = 2;
                        DurabilityModifier = 0.5;
                        break;

                    case BuffType.Progress:
                        buff.CurrentStack = 2;
                        ProgressModifier = 1.5;
                        break;

                    case BuffType.Quality:
                        buff.CurrentStack = 2;
                        QualityModifier = 1.5;
                        break;
                }
            }
        }
    }
}

Item class:

 public class Item
{
    public bool HasBuff { get; set; } = false;
    public int Weight { get; set; }
    public int Durability { get; set; }
    public int Progress { get; set; }
    public int Quality { get; set; }

    public Buff Buff = null;
}

Buff class:

public enum BuffType
{
    DurabilityRestoration,
    DurabilityModifier,
    Progress,
    Quality
}

public class Buff
{
    public int CurrentStack;
    public bool NeedsRemove { get; set; }

    public BuffType BuffType { get; private set; }
    public Buff(BuffType buffType)
    {
        BuffType = buffType;
    }

    public void Step(Knapsack knapsack)
    {
        CurrentStack--;
        if (CurrentStack == 0)
            NeedsRemove = true;
    }

}

Example of how to use it:

Knapsack knapsack = new Knapsack { MaxWeight = 100, Durability = 60, MaxProgress = 100, MaxQuality = 100 };

        Item[] items = new Item[]
        {
            new Item {Weight = 1, Durability = 10, Progress = 20, Quality = 0, HasBuff = false },
            new Item {Weight = 1, Durability = 0, Progress = 0, Quality = 0, HasBuff = true, Buff = new Buff(BuffType.DurabilityRestoration) },
            new Item {Weight = 4, Durability = 15, Progress = 5, Quality = 25, HasBuff = false },
            new Item {Weight = 3, Durability = -15, Progress = 0, Quality = 0, HasBuff = false },
            new Item {Weight = 1, Durability = 10, Progress = 0, Quality = 0, HasBuff = true, Buff = new Buff(BuffType.Progress) },
            new Item {Weight = 1, Durability = 10, Progress = 0, Quality = 0, HasBuff = true, Buff = new Buff(BuffType.Quality) },
        };

        knapsack.CurrentItems.Add(items[4]);
        knapsack.CurrentItems.Add(items[1]);
        knapsack.CurrentItems.Add(items[5]);
        knapsack.CurrentItems.Add(items[2]);
        knapsack.CurrentItems.Add(items[2]);
        knapsack.CurrentItems.Add(items[3]);
        knapsack.CurrentItems.Add(items[2]);
        knapsack.CurrentItems.Add(items[2]);
        knapsack.CurrentItems.Add(items[1]);
        knapsack.CurrentItems.Add(items[3]);
        knapsack.CurrentItems.Add(items[3]);
        knapsack.CurrentItems.Add(items[4]);
        knapsack.CurrentItems.Add(items[0]);
        knapsack.CurrentItems.Add(items[0]);
        knapsack.CurrentItems.Add(items[4]);
        knapsack.CurrentItems.Add(items[0]);
        knapsack.ExecuteItems();

What I want is an algorithm that solves the problem in most optimal way.

Answer 1

You've flagged the question as being C# and so I'd recommend that you use the power of it. So instead of using separate lists of Item properties, instead have an Item class that has those properties e.g.

interface IItem
{
  int Weight{get;set;}
  int Durability {get;set;}
  int Progress {get;set;}
  int Quality {get;set;}
  int Buff {get;set;}
}

class Item1 : IItem
{
  ...
}

class Item2 : IItem
{
  ...
}

…

then you KnapSack class can have a collection of IItem class which is the Contents.

Then if you have a full list of all unique IItem based classes you can order them by the property that you are interested in and select which one you may be able to fit in your KnapSack based on its criteria e.g. Weight might be too high and so you select an IItem that has a low weight.

---

edited

Okay your recent post has made my original post obsolete, hence why someone down voted it.

All the same I think that what you want is to perform some sort of Venn Diagram logic in code on the criteria that you have.

Let me explain.

Your goal is to reach the maximum quality and progress with the fewest number of items, so order all of your items by Quality (highest first) and keep adding instances from this ordered list to a Quality List until you have reached as close a possible to the maximum. If the current instance wont fit then step to the next in the list and check that.

Perform the same process on each of your Item properties.

Then you can determine where the Lists Intersect the resulting output will be close to your optimum selection of Items.

I have a distinct impression that you may want each of your Item types to be a unique class and that they each implement the same Interface or they have a property that indicates their type, if only so that you can determine which ones you have selected at the end.