01背包问题
01背包问题是算法竞赛中经典的dp题目。文中总共包含五个版本的代码。从最朴素的枚举法开始,在不断的改进下,最终变成了dp解法。
问题定义
有若干个物品,每件物品的有重量weight
和价值value
:
struct Item {
Int
weight : Int
Int
Int
value : Int
Int
}
现在,给定一个物品列表items
,和背包的容量capacity
。从中选出若干件物品,使得这些物品的总重量不超过背包的容量,且物品的总价值最大。
typealias enum @list.T[A] {
Empty
More(A, tail~ : @list.T[A])
}
@list.T as List
let @list.T[Item]
items_1 : enum @list.T[A] {
Empty
More(A, tail~ : @list.T[A])
}
List[struct Item {
weight: Int
value: Int
}
Item] = (arr : FixedArray[Item]) -> @list.T[Item]
@list.of([
{ Int
weight: 7, Int
value: 20 },
{ Int
weight: 4, Int
value: 10 },
{ Int
weight: 5, Int
value: 11 },
])
以上面的items_1
为例,假设背包容量是,那么最优的方案是选取后两个物品,占用的容量,总共有点价值。
注意,由于我们不能把物品切割,因此优先挑选性价比最高的物品并非正解。例如,在上面的例子中,若选取了性价比最高的物品1,则只有点价值,而此时背包已经放不下其他物品了。
问题建模
我们先定义一些基础的对象与操作。
//物品的组合,下文简称组合
struct Combination {
@list.T[Item]
items : enum @list.T[A] {
Empty
More(A, tail~ : @list.T[A])
}
List[struct Item {
weight: Int
value: Int
}
Item]
Int
total_weight : Int
Int
Int
total_value : Int
Int
}
//空的组合
let Combination
empty_combination : struct Combination {
items: @list.T[Item]
total_weight: Int
total_value: Int
}
Combination = {
@list.T[Item]
items: () -> @list.T[Item]
Creates an empty list
@list.empty(),
Int
total_weight: 0,
Int
total_value: 0,
}
//往组合中添加物品,得到新的组合
fn struct Combination {
items: @list.T[Item]
total_weight: Int
total_value: Int
}
Combination::(self : Combination, item : Item) -> Combination
add(Combination
self : struct Combination {
items: @list.T[Item]
total_weight: Int
total_value: Int
}
Combination, Item
item : struct Item {
weight: Int
value: Int
}
Item) -> struct Combination {
items: @list.T[Item]
total_weight: Int
total_value: Int
}
Combination {
{
@list.T[Item]
items: Combination
self.@list.T[Item]
items.(self : @list.T[Item], head : Item) -> @list.T[Item]
add(Item
item),
Int
total_weight: Combination
self.Int
total_weight (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:
self
: The first integer operand.
other
: The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
inspect(42 + 1, content="43")
inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ Item
item.Int
weight,
Int
total_value: Combination
self.Int
total_value (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:
self
: The first integer operand.
other
: The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
inspect(42 + 1, content="43")
inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ Item
item.Int
value,
}
}
//两个组合等效,意思是它们总价值一样
impl trait Eq {
op_equal(Self, Self) -> Bool
}
Trait for types whose elements can test for equality
Eq for struct Combination {
items: @list.T[Item]
total_weight: Int
total_value: Int
}
Combination with (self : Combination, other : Combination) -> Bool
op_equal(Combination
self, Combination
other) {
Combination
self.Int
total_value (self : Int, other : Int) -> Bool
Compares two integers for equality.
Parameters:
self
: The first integer to compare.
other
: The second integer to compare.
Returns true
if both integers have the same value, false
otherwise.
Example:
inspect(42 == 42, content="true")
inspect(42 == -42, content="false")
== Combination
other.Int
total_value
}
//比较两个组合的大小,就是比较它们总价值的大小
impl trait Compare {
compare(Self, Self) -> Int
}
Trait for types whose elements are ordered
The return value of [compare] is:
- zero, if the two arguments are equal
- negative, if the first argument is smaller
- positive, if the first argument is greater
Compare for struct Combination {
items: @list.T[Item]
total_weight: Int
total_value: Int
}
Combination with (self : Combination, other : Combination) -> Int
compare(Combination
self, Combination
other) {
Combination
self.Int
total_value.(self : Int, other : Int) -> Int
Compares two integers and returns their relative order.
Parameters:
self
: The first integer to compare.
other
: The second integer to compare against.
Returns an integer indicating the relative order:
- A negative value if
self
is less than other
- Zero if
self
equals other
- A positive value if
self
is greater than other
Example:
let a = 42
let b = 24
inspect(a.compare(b), content="1") // 42 > 24
inspect(b.compare(a), content="-1") // 24 < 42
inspect(a.compare(a), content="0") // 42 = 42
compare(Combination
other.Int
total_value)
}
然后,我们就可以开始思考如何解决问题了。
一、朴素的枚举
枚举法是最朴素的方案,我们依照问题的定义,一步一步执行,就能得到答案:
- 枚举出所有的组合;
- 过滤出其中有效的组合,也就是那些能装入背包的;
- 答案是其中总价值最大的那个。
得益于标准库提供的两个函数,我们可以将上面三行文字一比一地翻译为MoonBit代码。其中all_combinations
是我们后续需要实现的函数,它的类型是(List[Item]) -> List[Combination]
。
fn (items : @list.T[Item], capacity : Int) -> Combination
solve_v1(@list.T[Item]
items : enum @list.T[A] {
Empty
More(A, tail~ : @list.T[A])
}
List[struct Item {
weight: Int
value: Int
}
Item], Int
capacity : Int
Int) -> struct Combination {
items: @list.T[Item]
total_weight: Int
total_value: Int
}
Combination {
(items : @list.T[Item]) -> @list.T[Combination]
all_combinations(@list.T[Item]
items)
.(self : @list.T[Combination], f : (Combination) -> Bool) -> @list.T[Combination]
Filter the list.
Example
assert_eq(@list.of([1, 2, 3, 4, 5]).filter(fn(x){ x % 2 == 0}), @list.of([2, 4]))
filter(fn(Combination
comb) { Combination
comb.Int
total_weight (self_ : Int, other : Int) -> Bool
<= Int
capacity })
.(self : @list.T[Combination]) -> Combination
unsafe_maximum()
}
注意这里使用的是unsafe_maximum
而不是maximum
。这是因为空列表列表中没有最大值,maximum
在这种情况下会返回一个None
。但我们知道,题目保证答案存在(只要capacity不是负数),所以我们可以改用unsafe_maximum
。它在输入空列表的情况下直接中断程序,其它情况返回列表中的最大值。
接下来我们去实现枚举的过程。函数all_combinations
接受一个物品的列表,返回一个组合的列表,其中包含所有能由这些物品构造出的组合。也许你现在没有头绪,这时我们可以先查看一下列表的定义。它大概长这样:
enum List[A] {
Empty
More(A, tail~ : List[A])
}
也就是说,列表分为两种:
- 第一种是空的列表,叫
Empty
; - 第二种是非空的列表,叫
More
,其中包含了第一个元素(A
)和剩余的部分(tail~ : T[A]
),剩余部分也是一个列表。
这启示我们按物品列表是否为空来分情况讨论:
- 如果物品列表为空,那么唯一的一种组合方式就是空的组合;
- 否则,一定存在第一个物品
item1
和剩余部分items_tail
。这种情况下,我们可以:- 先求出不含
item1
的那些组合。这其实就是items_tail
能凑出的那些组合,可以递归地求出。 - 再求出包含
item1
的那些组合。它们与不含item1
的组合一一对应,只差把item1
加入其中。 - 将这两者合并起来,就是所有
items
能凑出的组合。
- 先求出不含
例如,当物品列表包含a,b,c三个元素时,答案分为以下两个部分:
不含a的部分 | 包含a的部分 |
---|---|
{ } | { a } |
{ b } | { a, b } |
{ c } | { a, c } |
{ b, c } | { a, b, c } |
fn (items : @list.T[Item]) -> @list.T[Combination]
all_combinations(@list.T[Item]
items : enum @list.T[A] {
Empty
More(A, tail~ : @list.T[A])
}
List[struct Item {
weight: Int
value: Int
}
Item]) -> enum @list.T[A] {
Empty
More(A, tail~ : @list.T[A])
}
List[struct Combination {
items: @list.T[Item]
total_weight: Int
total_value: Int
}
Combination] {
match @list.T[Item]
items {
@list.T[Item]
Empty => (x : Combination) -> @list.T[Combination]
@list.singleton(Combination
empty_combination)
(Item, @list.T[Item]) -> @list.T[Item]
More(Item
item1, @list.T[Item]
tail=@list.T[Item]
items_tail) => {
let @list.T[Combination]
combs_without_item1 = (items : @list.T[Item]) -> @list.T[Combination]
all_combinations(@list.T[Item]
items_tail)
let @list.T[Combination]
combs_with_item1 = @list.T[Combination]
combs_without_item1.(self : @list.T[Combination], f : (Combination) -> Combination) -> @list.T[Combination]
Maps the list.
Example
assert_eq(@list.of([1, 2, 3, 4, 5]).map(fn(x){ x * 2}), @list.of([2, 4, 6, 8, 10]))
map(_.(self : Combination, item : Item) -> Combination
add(Item
item1))
@list.T[Combination]
combs_with_item1 (self : @list.T[Combination], other : @list.T[Combination]) -> @list.T[Combination]
Concatenate two lists.
a + b
equal to a.concat(b)
+ @list.T[Combination]
combs_without_item1
}
}
}
通过使用模式匹配(match
),我们再一次将上面的五行文字一比一地翻译成了MoonBit代码。
二、提前过滤,仅枚举有效的组合
在第一个版本中,枚举所有组合和过滤出能放入背包的组合是不相干的两个过程。在枚举的过程中,出现了很多无效的组合。这些组合早已放不进背包中,却还在后续的过程中被添加物品。不如早一点过滤它们,避免在它之上不断产生新的无效组合。观察代码,发现无效的组合只会在.map(_.add(item1))
这一步产生。于是我们可以做出改进:仅向能再装下item1
的组合添加item1
。
我们将all_combinations
改为all_combinations_valid
,仅返回能装入这个背包的组合。现在枚举和过滤将交替进行。
fn (items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid(
@list.T[Item]
items : enum @list.T[A] {
Empty
More(A, tail~ : @list.T[A])
}
List[struct Item {
weight: Int
value: Int
}
Item],
Int
capacity : Int
Int // 添加一个参数,因为过滤需要知道背包的容量
) -> enum @list.T[A] {
Empty
More(A, tail~ : @list.T[A])
}
List[struct Combination {
items: @list.T[Item]
total_weight: Int
total_value: Int
}
Combination] {
match @list.T[Item]
items {
@list.T[Item]
Empty => (x : Combination) -> @list.T[Combination]
@list.singleton(Combination
empty_combination) // 空的组合自然是有效的
(Item, @list.T[Item]) -> @list.T[Item]
More(Item
item1, @list.T[Item]
tail=@list.T[Item]
items_tail) => {
// 我们假设 all_combinations_valid 返回的组合都是有效的(归纳假设)
let @list.T[Combination]
valid_combs_without_item1 = (items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid(
@list.T[Item]
items_tail, Int
capacity,
)
// 由于添加了过滤,所以它里面的组合都是有效的
let @list.T[Combination]
valid_combs_with_item1 = @list.T[Combination]
valid_combs_without_item1
.(self : @list.T[Combination], f : (Combination) -> Bool) -> @list.T[Combination]
Filter the list.
Example
assert_eq(@list.of([1, 2, 3, 4, 5]).filter(fn(x){ x % 2 == 0}), @list.of([2, 4]))
filter(fn(Combination
comb) { Combination
comb.Int
total_weight (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:
self
: The first integer operand.
other
: The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
inspect(42 + 1, content="43")
inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ Item
item1.Int
weight (self_ : Int, other : Int) -> Bool
<= Int
capacity })
.(self : @list.T[Combination], f : (Combination) -> Combination) -> @list.T[Combination]
Maps the list.
Example
assert_eq(@list.of([1, 2, 3, 4, 5]).map(fn(x){ x * 2}), @list.of([2, 4, 6, 8, 10]))
map(_.(self : Combination, item : Item) -> Combination
add(Item
item1))
// 两个部分都仅包含有效组合,所以合并后也仅包含有效组合
@list.T[Combination]
valid_combs_with_item1 (self : @list.T[Combination], other : @list.T[Combination]) -> @list.T[Combination]
Concatenate two lists.
a + b
equal to a.concat(b)
+ @list.T[Combination]
valid_combs_without_item1
}
}
}
遵循代码的结构进行分类讨论,很容易证明all_combinations_valid
的正确性——它返回的所有组合确实都是有效的。
由于all_combinations_valid
返回的那些组合都是有效的,就不再需要在solve
中过滤了。我们将solve
中的filter
删去。
fn (items : @list.T[Item], capacity : Int) -> Combination
solve_v2(@list.T[Item]
items : enum @list.T[A] {
Empty
More(A, tail~ : @list.T[A])
}
List[struct Item {
weight: Int
value: Int
}
Item], Int
capacity : Int
Int) -> struct Combination {
items: @list.T[Item]
total_weight: Int
total_value: Int
}
Combination {
(items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid(@list.T[Item]
items, Int
capacity).(self : @list.T[Combination]) -> Combination
unsafe_maximum()
}
三、维护升序性质,提前结束过滤
在上个版本中,为了过滤出那些能装下item1
的组合,我们必须遍历valid_combs_without_item1
中的每一个组合。
但我们可以发现:如果item1
没法放入一个组合,那么item1
一定都无法放入比这个组合总重量更大的那些组合。
这也就是说,如果valid_combs_without_item1
能按总重量升序排列,那么过滤时就不需要完整地遍历它了。在过滤的过程中,一旦碰到一个放不下item1
的组合,就可以立刻舍去后续的所有组合。由于这种逻辑很常见,标准库提供了一个叫take_while
的函数,我们用它替换掉filter
。
要想让valid_combs_without_item1
升序排列,可以用排序算法,但这却要遍历整个列表,违背了初衷。因此,我们得采用另一种方案:想办法让all_combinations_valid
返回的列表是升序的。这需要一次递归的信仰之跃:
fn (items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid_ordered(
@list.T[Item]
items : enum @list.T[A] {
Empty
More(A, tail~ : @list.T[A])
}
List[struct Item {
weight: Int
value: Int
}
Item],
Int
capacity : Int
Int
) -> enum @list.T[A] {
Empty
More(A, tail~ : @list.T[A])
}
List[struct Combination {
items: @list.T[Item]
total_weight: Int
total_value: Int
}
Combination] {
match @list.T[Item]
items {
@list.T[Item]
Empty => (x : Combination) -> @list.T[Combination]
@list.singleton(Combination
empty_combination) // 单元素的列表,自然是升序的
(Item, @list.T[Item]) -> @list.T[Item]
More(Item
item1, @list.T[Item]
tail=@list.T[Item]
items_tail) => {
// 我们假设 all_combinations_valid_ordered 返回的列表是升序的(归纳假设)
let @list.T[Combination]
valid_combs_without_item1 = (items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid_ordered(
@list.T[Item]
items_tail, Int
capacity,
)
// 那么它也是升序的,因为一个升序的列表先截取一部分,再往每个元素加上同样的重量,它们的总重量还是升序的
let @list.T[Combination]
valid_combs_with_item1 = @list.T[Combination]
valid_combs_without_item1
.(self : @list.T[Combination], p : (Combination) -> Bool) -> @list.T[Combination]
Take the longest prefix of a list of elements that satisfies a given predicate.
Example
let ls = @list.from_array([1, 2, 3, 4])
let r = ls.take_while(fn(x) { x < 3 })
assert_eq(r, @list.of([1, 2]))
take_while(fn(Combination
comb) { Combination
comb.Int
total_weight (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:
self
: The first integer operand.
other
: The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
inspect(42 + 1, content="43")
inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ Item
item1.Int
weight (self_ : Int, other : Int) -> Bool
<= Int
capacity })
.(self : @list.T[Combination], f : (Combination) -> Combination) -> @list.T[Combination]
Maps the list.
Example
assert_eq(@list.of([1, 2, 3, 4, 5]).map(fn(x){ x * 2}), @list.of([2, 4, 6, 8, 10]))
map(_.(self : Combination, item : Item) -> Combination
add(Item
item1))
// 现在我们只需要确保合并后也升序,就能衔接上最开始的假设
(a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order(@list.T[Combination]
valid_combs_with_item1, @list.T[Combination]
valid_combs_without_item1)
}
}
}
最后的任务是完成函数merge_keep_order
,它将两个升序的列表合并为一个升序的列表:
fn (a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order(
@list.T[Combination]
a : enum @list.T[A] {
Empty
More(A, tail~ : @list.T[A])
}
List[struct Combination {
items: @list.T[Item]
total_weight: Int
total_value: Int
}
Combination],
@list.T[Combination]
b : enum @list.T[A] {
Empty
More(A, tail~ : @list.T[A])
}
List[struct Combination {
items: @list.T[Item]
total_weight: Int
total_value: Int
}
Combination]
) -> enum @list.T[A] {
Empty
More(A, tail~ : @list.T[A])
}
List[struct Combination {
items: @list.T[Item]
total_weight: Int
total_value: Int
}
Combination] {
match (@list.T[Combination]
a, @list.T[Combination]
b) {
(@list.T[Combination]
Empty, @list.T[Combination]
another) | (@list.T[Combination]
another, @list.T[Combination]
Empty) => @list.T[Combination]
another
((Combination, @list.T[Combination]) -> @list.T[Combination]
More(Combination
a1, @list.T[Combination]
tail=@list.T[Combination]
a_tail), (Combination, @list.T[Combination]) -> @list.T[Combination]
More(Combination
b1, @list.T[Combination]
tail=@list.T[Combination]
b_tail)) =>
// 如果 a1 比 b1 更轻,而 b 又是升序的,说明
// a1 比 b 里所有组合都轻
// 由于 a 是升序的,所以
// a1 比 a_tail 里所有组合都轻
// 所以 a1 是 a 和 b 中最小的那一个
if Combination
a1.Int
total_weight (self_ : Int, other : Int) -> Bool
< Combination
b1.Int
total_weight {
// 我们先递归地合并出答案的剩余部分,再把 a1 加到开头
(a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order(@list.T[Combination]
a_tail, @list.T[Combination]
b).(self : @list.T[Combination], head : Combination) -> @list.T[Combination]
add(Combination
a1)
} else { // 同理
(a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order(@list.T[Combination]
a, @list.T[Combination]
b_tail).(self : @list.T[Combination], head : Combination) -> @list.T[Combination]
add(Combination
b1)
}
}
}
虽然看起来有点啰嗦,但我还是想提一句:通过遵循代码结构的分类讨论,很容易证明all_combinations_valid_ordered
和merge_keep_order
的正确性——它确实返回的一个升序的列表。
对于一个升序的列表,它的最大值就是最后一个。于是我们将unsafe_maximum
替换成unsafe_last
。
fn (items : @list.T[Item], capacity : Int) -> Combination
solve_v3(@list.T[Item]
items : enum @list.T[A] {
Empty
More(A, tail~ : @list.T[A])
}
List[struct Item {
weight: Int
value: Int
}
Item], Int
capacity : Int
Int) -> struct Combination {
items: @list.T[Item]
total_weight: Int
total_value: Int
}
Combination {
(items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid_ordered(@list.T[Item]
items, Int
capacity).(self : @list.T[Combination]) -> Combination
unsafe_last()
}
回过头来看,在这一版的改进中,我们似乎并没有得到什么太大的好处,毕竟在合并列表的过程中,我们仍然需要遍历整个列表。最初我也是这么想的,但后来意外地发现merge_keep_order
的真正作用在下一个版本。