问题求解II-HW13 题解

Problem A: 高楼抛鸡蛋

• 有一个 $n$ 层的高楼。存在一个未知的分界楼层 $X$，在 $1…X$ 层扔鸡蛋落地不会碎；在 $X+1$ 层以及更高的楼层扔鸡蛋落地会碎。问用 $k$ 个鸡蛋最少扔几次可以确定 $X$。
• $n\leq 10^4, k\leq 100$。

Problem B: 背包问题

• 有一个容积为 $v$ 的背包和 $n$ 个物品，第 $i$ 个物品的体积是 $v_i$，价值是 $w_i$。求用背包最多能装下多少价值的物品。
• $n\leq 500, v\leq 10^9, \sum w_i\leq 10^6$。

Problem C: Cache调度

• 有两块 Cache 和 $n$ 个程序，每个程序有一个类别 (共有 $k$ 种类别)，在同一块 Cache 上连续执行相同种类的程序第二次只需 $hot_i$ 的时间，否则需要 $cold_i$ 的时间。问串行执行所有程序所需的最小时间。
• $n, k\leq 5000$。