维基百科关于背包问题的文章包含三种类型：
1-0（一种类型的一项）
有界（一种类型的几个项目）
Unbounded（一种类型的项目数量不限）
该文章包含针对 1. 和 3. 类型问题的 DP 方法，但没有针对 2. 的解决方案。
如何描述求解 2. 的动态规划算法？
问问题
14093 次
6 回答
8
使用 0-1 变体，但允许解决方案中的项目重复到其界限中指定的次数。您需要维护一个向量，说明您已包含在部分解决方案中的每个项目的副本数。
于 2012-03-04T23:09:43.653 回答
6
提到的其他 DP 解决方案都是次优的，因为它们需要您直接模拟问题，从而导致O(number of items * maximum weight * total count of items)运行时复杂性。
有很多方法可以优化这一点，我将在这里提到其中的一些：
一种解决方案是应用类似于 Sqrt Decomposition 的技术，如下所述：https ://codeforces.com/blog/entry/59606 。该算法在O(number of items * maximum weight * sqrt(maximum weight)).
O(number of items * maximum weight * log(maximum weight))但是，Dorijan Lendvaj 描述了一种在此处运行的更快的算法： https ://codeforces.com/blog/entry/65202?#comment-492168
考虑上述方法的另一种方法如下：
对于每种类型的项目，让我们定义以下值：
w, 当前类型物品的重量/成本v，当前项目类型的值n, 可用的当前类型项目的副本数
阶段1
首先，让我们考虑小于或等于2^k的最大幂。我们插入以下项目（每个插入项目的格式为）：, , , ..., 。请注意，每个插入的项目分别代表当前类型项目的、、 ...、副本。2n(weight, value)(w, v)(2 * w, 2 * v)(2^2 * w, 2^2 * v)(2^(k-1) * w, 2^(k-1) * v)2^02^12^(k-1)
请注意，这与插入2^k - 1当前类型项目的副本相同。这是因为我们可以模拟取任意数量的项（n'表示为当前类型项目的副本）。n'k'2^k'2^k'
阶段2
最后，我们只插入与 的设置位相对应的项目n - (2^k - 1)。（对于所有整数k'，如果2^k'设置了表示的位，则插入(2^k' * w, 2^k' * v)）。
现在，我们可以简单地通过组合上述插入的项目来模拟最多n当前类型的项目。
我目前没有这个解决方案的确切证据，但是在玩了一段时间之后，它似乎是正确的。如果我能想出一个，我可能会稍后更新这篇文章。
证明
首先，一个命题：我们所要证明的是，插入上述项目允许我们模拟当前类型的任意数量的项目，最多为n.
考虑到这一点，让我们定义一些变量：
- 令
n为当前可用类型的项目数 - 让
x我们想要采取的当前类型的项目数 - 令
k为最大整数，使得2^k <= n
如果，我们可以使用算法阶段 1 中描述的方法x < 2^k轻松获取项目：x
...我们可以通过取与 n' 的二进制表示相对应的上述项目的组合来模拟任意数量的项目（表示为 n'）（对于所有整数 k'，如果位表示 2^ k' 已设置，取代表当前类型项目的 2^k' 个副本的项目）。
否则，我们执行以下操作：
拿n - (2^k - 1)东西。这是通过获取阶段 2 中插入的所有项目来完成的。现在只有阶段 1 中插入的项目可供使用。
拿x - (n - (2^k - 1))东西。由于这个值总是小于2^k，我们可以使用第一种情况的方法。
最后，我们怎么知道x - (n - (2^k - 1)) < 2^k呢？
如果我们简化左边，我们得到：
x - (n - (2^k - 1))
x - n + 2^k - 1
x - (n + 1) + 2^k
如果上述值为>= 2^k，x - (n + 1) >= 0则为真，即x > n。那是不可能的，因为这不是x.
最后，这里甚至提到了一种及时运行的方法O(number of items * maximum weight)。
该算法类似于ic3b3rg提出的蛮力方法，只是使用简单的 DP 优化和滑动窗口双端队列来降低运行时间。
我的代码在这个问题上进行了测试（经典的有界背包问题）：https ://dmoj.ca/problem/knapsack
于 2020-01-25T04:41:33.620 回答
3
我在 Code Project 上发表了一篇文章，讨论了有界背包算法的更有效解决方案。
来自文章：
在动态规划解中，m数组的每个位置都是容量j的子问题。在 0/1 算法中，对于每个子问题，我们考虑将每个项目的一个副本添加到背包中的价值。在下面的算法中，对于每个子问题，我们考虑添加适合的数量或每个项目的可用数量中的较小者的值。
我还增强了代码，以便我们可以确定优化的背包中的内容（而不仅仅是优化的值）。
ItemCollection[] ic = new ItemCollection[capacity + 1];
for(int i=0;i<=capacity;i++) ic[i] = new ItemCollection();
for(int i=0;i<items.Count;i++)
for(int j=capacity;j>=0;j--)
if(j >= items[i].Weight) {
int quantity = Math.Min(items[i].Quantity, j / items[i].Weight);
for(int k=1;k<=quantity;k++) {
ItemCollection lighterCollection = ic[j - k * items[i].Weight];
int testValue = lighterCollection.TotalValue + k * items[i].Value;
if(testValue > ic[j].TotalValue) (ic[j] = lighterCollection.Copy()).AddItem(items[i],k);
}
}
private class Item {
public string Description;
public int Weight;
public int Value;
public int Quantity;
public Item(string description, int weight, int value, int quantity) {
Description = description;
Weight = weight;
Value = value;
Quantity = quantity;
}
}
private class ItemCollection {
public Dictionary<string,int> Contents = new Dictionary<string,int>();
public int TotalValue;
public int TotalWeight;
public void AddItem(Item item,int quantity) {
if(Contents.ContainsKey(item.Description)) Contents[item.Description] += quantity;
else Contents[item.Description] = quantity;
TotalValue += quantity * item.Value;
TotalWeight += quantity * item.Weight;
}
public ItemCollection Copy() {
var ic = new ItemCollection();
ic.Contents = new Dictionary<string,int>(this.Contents);
ic.TotalValue = this.TotalValue;
ic.TotalWeight = this.TotalWeight;
return ic;
}
}
代码项目文章中的下载包含一个测试用例。
于 2014-01-14T22:38:57.687 回答
2
- 首先，将所有数据存储在一个数组中（重复）。
- 然后使用维基百科文章（1-0）中提到的第一种方法。
例如，尝试使用 { 2 (2 times), 4(3 times),...} 的有界背包等效于使用 {2, 2, 4, 4, 4,...} 求解 1-0 背包.
于 2016-11-24T11:58:57.773 回答
1
我会建议你使用背包分数贪婪方法算法。它的复杂度是 O(n log n) 并且是最好的算法之一。下面我在c#中提到了它的代码..
private static void Knapsack()
{
Console.WriteLine("************Kanpsack***************");
Console.WriteLine("Enter no of items");
int _noOfItems = Convert.ToInt32(Console.ReadLine());
int[] itemArray = new int[_noOfItems];
int[] weightArray = new int[_noOfItems];
int[] priceArray = new int[_noOfItems];
int[] fractionArray=new int[_noOfItems];
for(int i=0;i<_noOfItems;i++)
{
Console.WriteLine("[Item"+" "+(i+1)+"]");
Console.WriteLine("");
Console.WriteLine("Enter the Weight");
weightArray[i] = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Enter the Price");
priceArray[i] = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("");
itemArray[i] = i+1 ;
}//for loop
int temp;
Console.WriteLine(" ");
Console.WriteLine("ITEM" + " " + "WEIGHT" + " "+"PRICE");
Console.WriteLine(" ");
for(int i=0;i<_noOfItems;i++)
{
Console.WriteLine("Item"+" "+(i+1)+" "+weightArray[i]+" "+priceArray[i]);
Console.WriteLine(" ");
}//For Loop For Printing the value.......
//Caluclating Fraction for the Item............
for(int i=0;i<_noOfItems;i++)
{
fractionArray[i] = (priceArray[i] / weightArray[i]);
}
Console.WriteLine("Testing.............");
//sorting the Item on the basis of fraction value..........
//Bubble Sort To Sort the Process Priority
for (int i = 0; i < _noOfItems; i++)
{
for (int j = i + 1; j < _noOfItems; j++)
{
if (fractionArray[j] > fractionArray[i])
{
//item Array
temp = itemArray[j];
itemArray[j] = itemArray[i];
itemArray[i] = temp;
//Weight Array
temp = weightArray[j];
weightArray[j] = weightArray[i];
weightArray[i] = temp;
//Price Array
temp = priceArray[j];
priceArray[j] = priceArray[i];
priceArray[i] = temp;
//Fraction Array
temp = fractionArray[j];
fractionArray[j] = fractionArray[i];
fractionArray[i] = temp;
}//if
}//Inner for
}//outer For
// Printing its value..............After Sorting..............
Console.WriteLine(" ");
Console.WriteLine("ITEM" + " " + "WEIGHT" + " " + "PRICE" + " "+"Fraction");
Console.WriteLine(" ");
for (int i = 0; i < _noOfItems; i++)
{
Console.WriteLine("Item" + " " + (itemArray[i]) + " " + weightArray[i] + " " + priceArray[i] + " "+fractionArray[i]);
Console.WriteLine(" ");
}//For Loop For Printing the value.......
Console.WriteLine("");
Console.WriteLine("Enter the Capacity of Knapsack");
int _capacityKnapsack = Convert.ToInt32(Console.ReadLine());
// Creating the valuse for Solution
int k=0;
int fractionvalue = 0;
int[] _takingItemArray=new int[100];
int sum = 0,_totalPrice=0;
int l = 0;
int _capacity = _capacityKnapsack;
do
{
if(k>=_noOfItems)
{
k = 0;
}
if (_capacityKnapsack >= weightArray[k])
{
_takingItemArray[l] = weightArray[k];
_capacityKnapsack = _capacityKnapsack - weightArray[k];
_totalPrice += priceArray[k];
k++;
l++;
}
else
{
fractionvalue = fractionArray[k];
_takingItemArray[l] = _capacityKnapsack;
_totalPrice += _capacityKnapsack * fractionArray[k];
k++;
l++;
}
sum += _takingItemArray[l-1];
} while (sum != _capacity);
Console.WriteLine("");
Console.WriteLine("Value in Kg Are............");
Console.WriteLine("");
for (int i = 0; i < _takingItemArray.Length; i++)
{
if(_takingItemArray[i]!=0)
{
Console.WriteLine(_takingItemArray[i]);
Console.WriteLine("");
}
else
{
break;
}
enter code here
}//for loop
Console.WriteLine("Toatl Value is "+_totalPrice);
}//Method
于 2015-01-07T12:11:49.520 回答
0
我们可以使用 0/1 背包算法来跟踪每个物品的剩余物品数量；
我们也可以对无界背包算法做同样的事情来解决有界背包问题。
于 2019-04-07T14:36:40.210 回答