一个类似于背包问题的规划问题

Question

我在一些stackexchange站点上询问过这个问题，他们告诉我，我应该在这里询问提供的代码，如下所示：

整个问题就像背包问题，但却是扩展的。

有一个背包，上面有：

• 重量，
• 耐久性，
• max进度，
• max质量。

有些东西。每个项目都有:重量、耐久性损失或增加、有助于进步的价值、有助于质量的价值。

还有一些项目可以添加“迷”，如下所示：

• 增加的价值有助于背包的进展和/或质量下n项，
• 降低下n项的耐久性损失，
• 在选择下n项后增加耐久性。
• n取决于buff.

f 219

背包始于重量，耐用性，0进度，0质量。同样的项目可以任意次数挑选。

在挑选物品时：

• 背包增加重量，
• 背包增加进度，
• 背包增加质量，
• 背包丢失或增加耐久性。

F 229

同样的项目可以任意次数挑选。

如果:背包耐用性达到0，背包进度达到最大进度，背包因重量而不能容纳任何物品，则停止挑选物品。

目标是用最少的项目和重量达到最大质量和最大进步(如果你达到最大质量和最大进步，这意味着你已经解决了问题)。

有大约20个项目，所以蛮力将无法工作。

所提供的代码：

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%

这只是一个简单的示例代码。真正的计划包括20多个行动，进度和质量取决于其他变量和整个项目是相当大的，可能会使事情变得复杂。但是，如果您需要完整的源代码，则可以提供它。

我尝试过的是:使用遗传算法来寻找最优解，它成功了，但我想要一个数学解。使用动态规划，先解决质量问题，然后继续前进。事情变得复杂的项目，添加'buff'，因为他们没有实际价值。

来自实际项目的蛮力尝试：

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);
                }
            }
        }

这个循环遍历所有可能的解决方案，但它需要大量的时间。注意:Knapsack.AddItems(项目)添加项目并计算所有变量(权重、进度、质量、耐久性)，如果某些操作失败，则将其删除。

我尽量减少项目：

背包课程：

 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;
                }
            }
        }
    }
}

物品类别：

 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;
}

巴夫级：

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;
    }

}

如何使用它的示例：

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();

我想要的是一个以最优的方式解决问题的算法。

Answer 1

您已经将这个问题标记为C#，所以我建议您使用它的功能。因此，与其使用单独的项属性列表，不如使用具有这些属性的Item类。

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
{
  ...
}

…

然后您的KnapSack类可以有一个IItem类的集合，这是内容。

然后，如果您有所有唯一的基于IItem的类的完整列表，您可以根据您感兴趣的属性对它们进行排序，并根据它的标准选择您可以在KnapSack中安装的类，例如，权重可能太高，因此您选择了一个权重较低的IItem。

编辑的

好吧，你最近的帖子让我原来的帖子过时了，所以有人投了反对票。

尽管如此，我认为您想要的是在代码中对您所拥有的条件执行某种Venn逻辑。

让我解释一下。

您的目标是以最少的项目数量达到最大质量和进度，因此按质量(最高第一位)对所有项目进行排序，并继续将实例从这个排序列表中添加到质量列表中，直到您尽可能接近最大值为止。如果当前实例不合适，那么就转到列表中的下一个实例，并检查它。

对每个项属性执行相同的处理。

然后，您可以确定列表在何处相交，结果输出将接近您对项的最佳选择。

我有一个明显的印象，您可能希望您的每个项类型都是一个唯一的类，并且每个类都实现相同的接口，或者它们有一个属性来指示它们的类型，如果这样您就可以确定您在末尾选择了哪些类型。