维基百科上关于背包问题的文章列出了三种问题：
-
1-0（一种类型的一项）
-
有界（一种类型的几个项目）
-
无限制（一种类型的项目数量不限）
本文包含1的DP方法。和3。类型的问题，但没有2的解决方案。
如何用动态规划算法求解2。被描述？
使用0-1变体，但允许在解决方案中重复一个项目，直到其边界中指定的次数。您需要维护一个向量，说明部分解决方案中已包含的每个项目的副本数量。
提到的其他DP解决方案都是次优的，因为它们需要您直接模拟问题，从而导致O(number of items * maximum weight * total count of items)运行时的复杂性。
有很多方法可以优化这一点，我将在这里提到其中的几个：
一种解决方案是应用类似于Sqrt分解的技术，如下所述：https://codeforces.com/blog/entry/59606.该算法在CCD_ 2中运行。
然而，Dorijan Lendvaj在这里描述了一种在O(number of items * maximum weight * log(maximum weight))中运行的更快的算法：https://codeforces.com/blog/entry/65202?#comment-492168
考虑上述方法的另一种方法如下：
对于每种类型的项目，让我们定义以下值：
w，当前类型物料的重量/成本v，当前项目类型的值n，当前可使用项目类型的副本数
第1阶段
首先，让我们考虑2^k，2的最大功率小于或等于n。我们插入以下项目（每个插入的项目的格式为(weight, value)）：(w, v)、(2 * w, 2 * v)、(2^2 * w, 2^2 * v)。。。，(2^(k-1) * w, 2^(k-1) * v)。注意，插入的项目分别表示2^0、2^1、…、。。。，CCD_ 17分别复制当前类型的项目。
注意，这与插入当前项目类型的2^k - 1副本相同。这是因为我们可以通过取与O(number of items * maximum weight * sqrt(maximum weight))0的二进制表示相对应的上述项目的组合来模拟取任意数量的项目（表示为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
如果是x < 2^k，我们可以使用算法第1阶段中描述的方法轻松获取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 - 1x - (n + 1) + 2^k
如果上面的值是>= 2^k，那么x - (n + 1) >= 0将为真，这意味着x > n。这是不可能的，因为这不是x的有效值。
最后，这里甚至提到了一种在O(number of items * maximum weight)时间内运行的方法。
该算法类似于ic3b3rg提出的暴力方法，只使用简单的DP优化和滑动窗口deque来降低运行时间。
我的代码针对这个问题（经典有界背包问题）进行了测试：https://dmoj.ca/problem/knapsack
我的代码：https://pastebin.com/acezMrMY
我在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;
}
}
代码项目文章中的下载包括一个测试用例。
- 首先，将所有数据存储在一个数组中（重复）
- 然后使用维基百科文章中提到的第一种方法（1-0）
例如，尝试具有{2（2次），4（3次），…}的有界背包相当于求解具有{2，2，4，4，…｝的1-0背包。
我建议您使用背包分数贪婪方法算法。它的复杂度是O（nlogn），是最好的算法之一。下面我在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
我们可以使用0/1背包算法来跟踪每个物品的剩余物品数量；
我们也可以用无界背包算法来求解有界背包问题。