我正在研究一个必须处理背包/子集求和问题的特殊情况的问题。问题如下:
您有一组随机递减的 bundle 大小，例如:{47, 35, 22, ...}。您的值是小部件的数量，例如:#widgets = 33。
找到最少数量的 bundle ，这些 bundle 可以构成 bundle 的小部件数量。如果无法返回等于数量的集合，则返回 null。
- 示例 1:
- bundle 大小:46、25、12、4、3
- 数量:30
- 返回值:{46:0、25:0、12:2、4:0、3:2}( bundle 大小: bundle 数量)
- 示例 2:
- bundle 大小:46、25、12、4、3
- 数量:17
- 返回值:{46:0、25:0、12:0、4:2、3:3}
- 示例 3:
- bundle 大小:46、25、12、4、3
- 数量:47
- 返回值:{46:0、25:1、12:1、4:1、3:2}
- 示例 4:
- bundle 大小:46、25、12、4、3
- 数量:5
- 返回值:null
如何解决这个问题？
我已经用 C# 编写了一个程序，该程序确实完成了足够的工作，但在 for 循环中重置了一个索引以转储无法与集合的其余部分一起使用的包大小。如果要求它走了多远，将发布源代码。
请求代码:
public List<int> BreakDown(List<int> bunSize, int buySize)
{
List<int> tempBunSize = bunSize.ToList();
tempBunSize.RemoveAll(e => e > buySize);
List<int> ammountNeeded = new List<int>();
int result = buySize;
for (int index = 0; index < tempBunSize.Count; index++)
{
int size = tempBunSize[index];
int tempResult = 0;
double calcResult = 0;
int addAmmount = 0;
if (index == tempBunSize.Count - 2)
{
tempResult = result % size;
if ((tempBunSize.Count > 2 || result % tempBunSize[tempBunSize.Count - 1] == 0))
{
if (result % size != 0)
{
ammountNeeded.Add(0);
tempResult = result % tempBunSize[tempBunSize.Count - 1];
if (tempResult != 0)
{
tempResult = result;
int sizeInc = 0;
while (tempResult != 0)
{
tempResult = tempResult - size;
sizeInc++;
if (tempResult < 0)
{
int decreaseOne = ammountNeeded.First();
ammountNeeded[0] = --decreaseOne;
result = result + tempBunSize.First();
if (ammountNeeded[0] <= 0)
{
tempBunSize.RemoveAt(0);
index = 0;
ammountNeeded = new List<int>();
}
ammountNeeded.Remove(0);
--index;
break;
}
if (tempResult % tempBunSize[tempBunSize.Count - 1] == 0)
{
ammountNeeded.Remove(0);
ammountNeeded.Add(sizeInc);
ammountNeeded.Add(tempResult / tempBunSize[tempBunSize.Count - 1]);
break;
}
}
if (tempResult < 0) continue;
break;
}
else
{
calcResult = result / tempBunSize[tempBunSize.Count - 1];
addAmmount = (int)Math.Floor(calcResult);
ammountNeeded.Add(addAmmount);
break;
}
}
else if (result % size == 0)
{
tempResult = result % size;
if (tempResult != 0 && result % tempBunSize[tempBunSize.Count - 1] != 0)
{
int decreaseOne = ammountNeeded.First();
ammountNeeded.Insert(0, --decreaseOne);
result = result + tempBunSize.First();
continue;
}
else
{
calcResult = result / size;
addAmmount = (int)Math.Floor(calcResult);
ammountNeeded.Add(addAmmount);
if (result % size == 0)
{
ammountNeeded.Add(0);
break;
}
calcResult = result / tempBunSize[tempBunSize.Count - 1];
addAmmount = (int)Math.Floor(calcResult);
ammountNeeded.Add(addAmmount);
break;
}
}
}
else if (tempResult % tempBunSize[tempBunSize.Count - 1] != 0)
{
tempResult = result;
int sizeInc = 0;
while (tempResult != 0)
{
tempResult = tempResult - size;
sizeInc++;
if (tempResult % tempBunSize[tempBunSize.Count - 1] == 0)
{
ammountNeeded.Add(sizeInc);
ammountNeeded.Add(tempResult / tempBunSize[tempBunSize.Count - 1]);
break;
}
}
break;
}
else if (result == 0)
{
while (ammountNeeded.Count < bunSize.Count)
{
ammountNeeded.Add(0);
}
break;
}
else
{
calcResult = result / size;
ammountNeeded.Add((int)Math.Floor(calcResult));
calcResult = tempResult / tempBunSize[tempBunSize.Count - 1];
ammountNeeded.Add((int)Math.Floor(calcResult));
break;
}
}
ammountNeeded.Add((int)Math.Floor((decimal)result / size));
result = result % size;
if (result == 0) continue;
}
if (ammountNeeded.Count < bunSize.Count)
{
ammountNeeded.Reverse(0, ammountNeeded.Count);
while (ammountNeeded.Count < bunSize.Count)
{
ammountNeeded.Add(0);
}
ammountNeeded.Reverse(0, ammountNeeded.Count);
}
if (ammountNeeded.FindLast(e => e < 0) < 0 || ammountNeeded.Sum() == 0)
return null;
return ammountNeeded;
}
}
最佳答案
这是一个需要解决的有趣问题。到处都是极客点。
我认为您的主要问题在于尝试遍历单个列表。您真正想要的是测试列表的所有变体，然后找到具有最高值的变体。
此外，正如评论中所述，递归是您的 friend 。我递归遍历了捆绑数量的每个排列。
您的数据存在的一个问题是您的 17 示例。这个例子中使用的数学是贪婪的。意思是，4 将在将剩余的交给 3 之前尝试获得尽可能多的包。因此 4 获得 4 个包，剩余 1 个包返回 null。出于这个原因，我认为 17 的正确答案应该是 null。您可能能够弄清楚如何在数字之间取得平衡，但在我看来，这将更加符合逻辑。
代码如下:
public class test
{
public static void Main()
{
var bundleSizes = new List<int> { 46, 25, 12, 4, 3 };
var quantity = 30;
var bundleResults = Begin(bundleSizes, quantity);
Output(bundleSizes, quantity, bundleResults);
quantity = 17;
bundleResults = Begin(bundleSizes, quantity);
Output(bundleSizes, quantity, bundleResults);
quantity = 47;
bundleResults = Begin(bundleSizes, quantity);
Output(bundleSizes, quantity, bundleResults);
quantity = 5;
bundleResults = Begin(bundleSizes, quantity);
Output(bundleSizes, quantity, bundleResults);
Console.Read();
}
static void Output(List<int> bundleSizes, int quantity, Dictionary<int, int> bundleResults)
{
var fullResults = new Dictionary<int, int>();
bundleSizes.ForEach(
delegate(int e)
{
var result = 0;
if(bundleResults != null)
bundleResults.TryGetValue(e, out result);
fullResults.Add(e, result);
});
Console.WriteLine("Bundle Sizes: {0}", string.Join(",", bundleSizes));
Console.WriteLine("Quantity: {0}", quantity);
Console.WriteLine("Returned Value: {0}", bundleResults == null ? "null" : fullResults.Aggregate("", (keyString, pair) => keyString + pair.Key + ":" + pair.Value + ","));
}
static Dictionary<int, int> Begin(List<int> bundleSizes, int quantity)
{
var bundleCombinations = GetCombination(bundleSizes);
var tempBundleSizes = new List<Dictionary<int, int>>();
foreach (var bundleCombination in bundleCombinations)
{
var tempBundleSize = new Dictionary<int, int>();
bundleCombination.ForEach(e => tempBundleSize.Add(e, 0));
var results = Bundle(bundleCombination, quantity);
if (results == null)
continue;
foreach (var result in results)
{
tempBundleSize[result.Key] = result.Value;
}
tempBundleSizes.Add(tempBundleSize);
}
var longest = tempBundleSizes.OrderByDescending(x => x.Count).FirstOrDefault();
return longest;
}
static List<List<int>> GetCombination(List<int> list)
{
var retValue = new List<List<int>>();
var count = Math.Pow(2, list.Count);
for (var i = 1; i <= count - 1; i++)
{
var retList = new List<int>();
var str = Convert.ToString(i, 2).PadLeft(list.Count, '0');
for (var j = 0; j < str.Length; j++)
{
if (str[j] == '1')
{
retList.Add(list[j]);
}
}
retValue.Add(retList);
}
return retValue;
}
static Dictionary<int, int> Bundle(List<int> bundleSizes, int quantity)
{
var bundleQuantities = new Dictionary<int, int>();
bundleSizes.ForEach(delegate(int k)
{
if (k <= quantity)
bundleQuantities.Add(k, 0);
});
return bundleQuantities.Count == 0 ? null : RecurseBundles(quantity, bundleQuantities.Keys.ToList(), bundleQuantities);
}
static Dictionary<int, int> RecurseBundles(int quantity, List<int> bundleSizes, Dictionary<int, int> bundleQuantities)
{
var bundleSize = bundleSizes.First();
var bundles = (int)Math.Floor((double)quantity / bundleSize);
var remainingQuantity = quantity % bundleSize;
bundleQuantities[bundleSize] = bundles;
var remainingBundles = bundleSizes.Skip(1).ToList();
if (!remainingBundles.Any() && remainingQuantity > 0)
bundleQuantities = null;
if (remainingBundles.Any())
bundleQuantities = RecurseBundles(remainingQuantity, remainingBundles, bundleQuantities);
return bundleQuantities;
}
}
这是输出:
Bundle Sizes: 46,25,12,4,3
Quantity: 30
Returned Value: 46:0,25:0,12:2,4:0,3:2,
Bundle Sizes: 46,25,12,4,3
Quantity: 17
Returned Value: null
Bundle Sizes: 46,25,12,4,3
Quantity: 47
Returned Value: 46:0,25:0,12:3,4:2,3:1,
Bundle Sizes: 46,25,12,4,3
Quantity: 5
Returned Value: null
特别感谢这些出色的 SO 答案:
All Possible Combinations of a list of Values
How do I combine the keys and values of a Dictionary into one List using LINQ?
Find max count of a list of custom types
编辑:在 Output 方法中做了一个小改动以获得更好的格式化输出
关于c# - 具有相同权重/值的修改后的背包/子集和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20107574/