我已经在某些stackexchange网站上询问了此问题,他们告诉我,我应该在此处询问提供的代码,所以在这里是:
整个问题就像背包问题,但是扩展了。
有一个背包:
体重,
耐久性,
最大进度,
最高质量。
有项目。每个项目都有:重量,耐久性的损失或增加,有助于进步的价值,有助于质量的价值。
也有一些添加'buff'的项目:
增加背负背包的进度和/或质量的价值对于接下来的n个项目,
减少下n个项目的耐久性损失,
在接下来的n个项目中添加耐久度。
n取决于增益。
背包从重量,耐用性,0进度,0质量开始。相同项目可以任意选择次数。
同时选择项目:
背包增加体重,
背包有进步,
背包提高品质,
背包失去或获得了耐久力。
相同项目可以被选择任意次。
如果发生以下情况,您将停止领取物品:背包的耐用性达到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(items)添加项目并计算所有变量(重量,进度,质量,耐用性),如果某些操作失败,则将其删除。
我最小化的项目:
背包类:
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;
}
Buff等级:
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();
您已将问题标记为C#,因此,我建议您使用它的功能。因此,与其使用单独的Item属性列表,不如使用具有这些属性的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
。