试题来源:https://koi.or.kr/archives/。中文翻译做了少量本土化修改。
按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。
商户是在 KOI 市经营商店的一位市民。商户的店里有 件商品,其中第 件商品的重量为 。商户收到了情报,得知小偷“金基范”正觊觎自己的店铺,于是他准备采取措施,将损失降到最低。
小偷金基范计划从店里偷走 件商品。但如果商品太重,不仅难以偷窃,被警察抓住的可能性也会变高。因此,小偷金基范会最小化他所偷商品的总重量。不过,如果店里的商品总数不足 件,小偷金基范会偷走店里所有的商品。
在小偷金基范到达店铺之前,商户会把店里的一些商品装进一个包里带走。之后,小偷金基范会对商户没有带走的那些商品,以上述方式实施盗窃。商户希望通过合理地往包里装商品,来最大化小偷金基范最终偷走的商品总重量。
商户的包能承受的重量是有限的。当给定一个最大承重 时,请对所有的 回答以下问题:
- 在商户能放入包中的商品总重量不超过 的条件下,小偷金基范偷走的商品总重量的最大值是多少?