01 背包问题是一个算法竞赛中经典的组合优化的问题,小 w 学会了一种求解该问题的贪心算法。01 背包问题的定义以及小 w 的贪心算法如下。
:
给定 个物品,物品的重量分别为正整数 ,物品的价值分别为正整数 ,再给定背包容量 。要求 (, ),满足:
并最大化:
:
- 将 个物品按照 的值从大到小排序, 相同则按照 从大到小排序。
- 设一初始置 0 的变量 ,并,并从 到 枚举 ,如果 ,则置 ,否则置 。
- 枚举完之后即可得到所求的 以及 。
你当然知道这个算法是错误的,但小 w 并不相信。即使你给了小 w 一些反例,小 w 依然认为这个算法能在很多不同的 下都能得到最优的 ,所以你现在希望构造一组 以及 使得:
- ( 是一个给定的常数),小 w 的算法都无法得到最优的 。
- 在满足条件 的情况下, 尽量小。
- 在满足条件 的情况下, 尽量小。
- 在满足条件 的情况下, 尽量小。
现在你需要构造一组满足上述条件的 01 背包来说服小 w,你能做到吗?如果构造方法有多种,你可以输出任意一种。