有界背包算法

• 下载源代码 - 1.2 KB

Using the Code

附件是一个用 C# 编写的 HttpHandler 。

引言

解决有界背包问题的常见方法是将输入转换为 0/1 背包问题。本文提出了一种更有效处理有界背包问题的方法。

背景

背包问题 旨在最大化放入有限容量背包中的物品的组合价值。背包问题有着悠久的历史，至少可以追溯到 1897 年，甚至更早。

对于单个背包，问题有三个基本版本

• 无界
• 0/1
• 有界

无界背包问题相对容易解决

1. 确定每个物品的价值重量比。
2. 从价值重量比最高的物品开始，将尽可能多的该物品放入背包。
3. 移动到下一个价值重量比最高的物品，并重复步骤 2，直到背包装满或没有其他物品。

问题的 0/1 版本为每个物品引入了 1 的界限；你将物品放入背包，或者不放入。维基百科上列出的动态规划伪代码是解决该问题的一种有效方法。这是 C# 的一维数组版本

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)

int[] m = new int[W + 1];

for(int i=0;i<n;i++)
  for(int j=W;j>=0;j--)
    m[j] = j < w[i] ? m[j] : Math.Max(m[j], m[j - w[i]] + v[i]);

容量 W 的优化值存储在 m[W] 中。

维基百科指出，0/1 版本是正在解决的最常见的问题。在我看来，具有不同数量的物品的有界版本是一种更现实的情况。在 这里 和 这里 进行 搜索 表明，处理有界背包问题的常用方法是将输入转换为 0/1 算法。我提出了一种更有效处理问题的方法。

解释

在动态规划解决方案中，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;
  }

}

测试

输入

var items = new List<Item>(){
  new Item("Apple", 39, 40, 4),
  new Item("Banana", 27, 60, 4),
  new Item("Beer", 52, 10, 12),
  new Item("Book", 30, 10, 2),
  new Item("Camera", 32, 30, 1),
  new Item("Cheese", 23, 30, 4),
  new Item("Chocolate Bar", 15, 60, 10),
  new Item("Compass", 13, 35, 1),
  new Item("Jeans", 48, 10, 1),
  new Item("Map", 9, 150, 1),
  new Item("Notebook", 22, 80, 1),
  new Item("Sandwich", 50, 160, 4),
  new Item("Ski Jacket", 43, 75, 1),
  new Item("Ski Pants", 42, 70, 1),
  new Item("Socks", 4, 50, 2),
  new Item("Sunglasses", 7, 20, 1),
  new Item("Suntan Lotion", 11, 70, 1),
  new Item("T-Shirt", 24, 15, 1),
  new Item("Tin", 68, 45, 1),
  new Item("Towel", 18, 12, 1),
  new Item("Umbrella", 73, 40, 1),
  new Item("Water", 153, 200, 1)
};

int capacity = 1000;

输出

背包容量：1000

填充重量：999

填充价值：2535

目录

• 苹果 (3)
• 香蕉 (4)
• 奶酪 (4)
• 巧克力棒 (10)
• 指南针 (1)
• 地图 (1)
• 笔记本 (1)
• 三明治 (4)
• 滑雪夹克 (1)
• 滑雪裤 (1)
• 袜子 (2)
• 太阳镜 (1)
• 防晒霜 (1)
• T 恤 (1)
• 水 (1)

注意： 方括号中的数字表示放入背包中每个物品的数量。