跳到主要内容

01背包问题

· 阅读需 13 分钟

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为例,假设背包容量是1010,那么最优的方案是选取后两个物品,占用4+5=94+5=9的容量,总共有10+11=2110+11=21点价值。

注意,由于我们不能把物品切割,因此优先挑选性价比最高的物品并非正解。例如,在上面的例子中,若选取了性价比最高的物品1,则只有2020点价值,而此时背包已经放不下其他物品了。

问题建模

我们先定义一些基础的对象与操作。

//物品的组合,下文简称组合
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
)
}

然后,我们就可以开始思考如何解决问题了。

一、朴素的枚举

枚举法是最朴素的方案,我们依照问题的定义,一步一步执行,就能得到答案:

  1. 枚举出所有的组合;
  2. 过滤出其中有效的组合,也就是那些能装入背包的;
  3. 答案是其中总价值最大的那个。

得益于标准库提供的两个函数,我们可以将上面三行文字一比一地翻译为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])
}

也就是说,列表分为两种:

  1. 第一种是空的列表,叫Empty
  2. 第二种是非空的列表,叫More,其中包含了第一个元素(A)和剩余的部分(tail~ : T[A]),剩余部分也是一个列表。

这启示我们按物品列表是否为空来分情况讨论:

  • 如果物品列表为空,那么唯一的一种组合方式就是空的组合;
  • 否则,一定存在第一个物品item1和剩余部分items_tail。这种情况下,我们可以:
    1. 先求出不含item1的那些组合。这其实就是items_tail能凑出的那些组合,可以递归地求出。
    2. 再求出包含item1的那些组合。它们与不含item1的组合一一对应,只差把item1加入其中。
    3. 将这两者合并起来,就是所有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_orderedmerge_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的真正作用在下一个版本。

四、去除等同重量的冗余组合,达到最优时间复杂度

目前为止,我们进行的都不是时间复杂度层面的优化,但这些优化恰恰为接下来的步骤铺平了道路。现在让我们来考察一下时间复杂度。

在最差情况下(背包很大,全都放得下),组合列表(all_combinations的返回值)将最多包含 2物品数量2^{物品数量} 个元素。这导致整个算法的时间复杂度也是指数级的,因为all_combinations会被调用 物品数量物品数量 次,而每次都会遍历组合列表。

为了降低时间复杂度,我们就需要降低组合列表的长度。这基于一个观察:如果有两个组合,它们总重量相同,那么总价值更高的那个组合总是比另一个更好。因此,我们不需要在列表中同时保留两者。

如果能排除那些冗余的组合,组合列表的长度将不会超过背包容量(抽屉原理),进而将整个算法的时间复杂度降低到 O(物品数量×背包容量)\mathcal{O}(物品数量 \times 背包容量)。观察代码,现在唯一有可能会向列表中引入冗余组合的地方是merge_keep_orderelse分支。为了避免这种情况出现,我们只需要对这个地方进行一点改动:

fnalias 
(x : T, y : T) -> T

Compares and returns the maximum of two values.

Returns the second argument if the comparison determines them to be equal.

Examples

  assert_eq(@math.maximum(1, 2), 2)
  assert_eq(@math.maximum(2, 2), 2)
@math.maximum
fn
(a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order_and_dedup
(
@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
)) =>
if
Combination
a1
.
Int
total_weight
(self_ : Int, other : Int) -> Bool
<
Combination
b1
.
Int
total_weight
{
(a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order_and_dedup
(
@list.T[Combination]
a_tail
,
@list.T[Combination]
b
).
(self : @list.T[Combination], head : Combination) -> @list.T[Combination]
add
(
Combination
a1
)
} else if
Combination
a1
.
Int
total_weight
(self_ : Int, other : Int) -> Bool
>
Combination
b1
.
Int
total_weight
{
(a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order_and_dedup
(
@list.T[Combination]
a
,
@list.T[Combination]
b_tail
).
(self : @list.T[Combination], head : Combination) -> @list.T[Combination]
add
(
Combination
b1
)
} else { // 此时 a1 和 b1 一样重,出现冗余,保留总价值更高的那个 let
Combination
better
=
(x : Combination, y : Combination) -> Combination

Compares and returns the maximum of two values.

Returns the second argument if the comparison determines them to be equal.

Examples

  assert_eq(@math.maximum(1, 2), 2)
  assert_eq(@math.maximum(2, 2), 2)
maximum
(
Combination
a1
,
Combination
b1
)
(a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order_and_dedup
(
@list.T[Combination]
a_tail
,
@list.T[Combination]
b_tail
).
(self : @list.T[Combination], head : Combination) -> @list.T[Combination]
add
(
Combination
better
)
} } }

all_combinations_valid_ordered_nodup(这是我这辈子写过的名字最长的函数了)和solve_v4替换相应部分即可。

fn 
(items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid_ordered_nodup
(
@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
) => {
let
@list.T[Combination]
combs_without_item1
=
(items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid_ordered_nodup
(
@list.T[Item]
items_tail
,
Int
capacity
,
) let
@list.T[Combination]
combs_with_item1
=
@list.T[Combination]
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_and_dedup
(
@list.T[Combination]
combs_with_item1
,
@list.T[Combination]
combs_without_item1
)
} } } fn
(items : @list.T[Item], capacity : Int) -> Combination
solve_v4
(
@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_nodup
(
@list.T[Item]
items
,
Int
capacity
).
(self : @list.T[Combination]) -> Combination
unsafe_last
()
}

至此,我们重新发明了01背包问题的dp解法。

总结

这篇文章的内容是我某天早上躺在床上的突发奇想,从第一版到第四版代码完全在手机上写成,没有经过任何调试,但却能轻松地保证了正确性。相比传统算法竞赛题解中常见的写法,本文中使用的函数式写法带来了以下优势:

  1. 告别循环,使用递归分情况讨论。要想从列表中获取元素,必须使用模式匹配(match),这提醒我考虑列表为空时的答案。它相比dp数组的初始值拥有更加明确的含义。
  2. 依赖库函数进行遍历。标准库中提供的高阶函数(filtertake_whilemapmaximum)能替换掉样板化的循环(forwhile),便于读者一眼看出遍历的目的。
  3. 声明式编程。第一版的代码是想法的一比一地翻译。与其说是在描述一个算法,更像是在描述这个问题本身,这保证了第一版的正确性。而随后每次改进都在不影响结果的前提下进行,于是继承了第一版的正确性。

当然,从来就没有银弹。我们需要可读性和效率之间做取舍。函数式的风格固然好理解,但还是有许多优化余地的。进一步的优化方向是将列表替换成数组,再替换成从头到尾只使用两个滚动数组,甚至是只使用一个数组。这可以将空间复杂度优化成 O(背包容量)\mathcal{O}(背包容量),但不在本文的讨论范围内。我相信初学者更希望看到的是一个易于理解的代码。

附录

更多细节优化

利用items中物品的顺序不影响结果的总价值这个性质。可以把all_combinations转化成尾递归。

另外,take_while产生的列表在map后马上就被丢弃了,我们可以改用迭代器来避免产生这个一次性列表。

fn 
(items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_loop
(
@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
] {
loop
@list.T[Item]
items
,
(x : Combination) -> @list.T[Combination]
@list.singleton
(
Combination
empty_combination
) {
@list.T[Item]
Empty
,
@list.T[Combination]
combs_so_far
=>
@list.T[Combination]
combs_so_far
(Item, @list.T[Item]) -> @list.T[Item]
More
(
Item
item1
,
@list.T[Item]
tail
=
@list.T[Item]
items_tail
),
@list.T[Combination]
combs_so_far
=> {
let
@list.T[Combination]
combs_without_item1
=
@list.T[Combination]
combs_so_far
let
@list.T[Combination]
combs_with_item1
=
@list.T[Combination]
combs_without_item1
.
(self : @list.T[Combination]) -> Iter[Combination]
iter
()
.
(self : Iter[Combination], f : (Combination) -> Bool) -> Iter[Combination]

Takes elements from the iterator as long as the predicate function returns true.

Type Parameters

  • T: The type of the elements in the iterator.

Arguments

  • self - The input iterator.
  • f - The predicate function that determines whether an element should be taken.

Returns

A new iterator that contains the elements as long as the predicate function returns true.

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 : Iter[Combination], f : (Combination) -> Combination) -> Iter[Combination]

Transforms the elements of the iterator using a mapping function.

Type Parameters

  • T: The type of the elements in the iterator.
  • R: The type of the transformed elements.

Arguments

  • self - The input iterator.
  • f - The mapping function that transforms each element of the iterator.

Returns

A new iterator that contains the transformed elements.

map
(_.
(self : Combination, item : Item) -> Combination
add
(
Item
item1
))
|>
(iter : Iter[Combination]) -> @list.T[Combination]

Convert the iterator into a list. Preserves order of elements. If the order of elements is not important, use from_iter_rev instead.

@list.from_iter
continue
@list.T[Item]
items_tail
,
(a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order_and_dedup
(
@list.T[Combination]
combs_with_item1
,
@list.T[Combination]
combs_without_item1
)
} } } fn
(items : @list.T[Item], capacity : Int) -> Combination
solve_v5
(
@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_loop
(
@list.T[Item]
items
,
Int
capacity
).
(self : @list.T[Combination]) -> Combination
unsafe_last
()
}

题外话

  1. 在第一版中,all_combinations(items)产生的Combination甚至比其中的More还多一个,堪称链表节点复用大师。
  2. 升序还可以换成降序,对应的take_while要换成drop_while。而改用Array后可以通过binary_search来寻找下标直接切分。
  3. 如果你感兴趣,可以考虑一下怎么把上面的做法拓展到各种其它的背包问题
  4. all_combinations_loop原名:generate_all_ordered_combination_that_fit_in_backpack_list_without_duplicates_using_loop

测试

test {
  for 
(@list.T[Item], Int) -> Combination
solve
in [
(items : @list.T[Item], capacity : Int) -> Combination
solve_v1
,
(items : @list.T[Item], capacity : Int) -> Combination
solve_v2
,
(items : @list.T[Item], capacity : Int) -> Combination
solve_v3
,
(items : @list.T[Item], capacity : Int) -> Combination
solve_v4
,
(items : @list.T[Item], capacity : Int) -> Combination
solve_v5
] {
(a : Int, b : Int, loc~ : SourceLoc = _) -> Unit raise Error

Asserts that two values are equal. If they are not equal, raises a failure with a message containing the source location and the values being compared.

Parameters:

  • a : First value to compare.
  • b : Second value to compare.
  • loc : Source location information to include in failure messages. This is usually automatically provided by the compiler.

Throws a Failure error if the values are not equal, with a message showing the location of the failing assertion and the actual values that were compared.

Example:

  assert_eq(1, 1)
  assert_eq("hello", "hello")
assert_eq
(
(@list.T[Item], Int) -> Combination
solve
(
@list.T[Item]
items_1
, 10).
Int
total_value
, 21)
} }