月度归档:2017年11月

动态规划-完全背包问题

Description

有 n 个重量和价值分别为 wi, vi 的物品。从这些物品中挑选出总重量不超过 W 的物品,求所有挑选方案中价值总和的最大值。在这里,每种物品可以挑选任意多件。

Input

第一行为 n 和 W, 1 ≤ n ≤ 100, 1 ≤ W ≤ 10000
之后 n 行每行为 w[……]

Read more

C 由实现定义的行为、未定义的行为与未明确的行为

Implementation-defined behavior

由实现定义的行为。例如,int 数据类型的内存空间大小为一般为 4 bytes。

Undefined behavior

未定义的行为。如果程序违反(或者超出) C 标准的规则定义,其执行的结果是无法预料的,换言之,对于这段语句,编译器不[……]

Read more

区间调度问题

Description

有 n 项工作,每项工作分别在 si 时间开始,在 ti 时间结束。对于每项工作,你都可以选择参与否。如果选择了参与,那么自始至终都必须全程参与。此外,参与工作的时间段不能重叠(既是是开始的瞬间和结束的瞬间重叠也是不允许的)

你的目标是参与尽可能多的工作,那么最多能参与多少项[……]

Read more