水杯倒水，计算最少的溢出量

2019/9/29镜像同步4 回复

现在有k个盛满水的杯子，每个杯子的容量为vol[i] （杯子的容量可重复）然后有一个大水杯，杯子容量为target 需要将用这k个杯子将大水杯装满水，每次倾倒必须倒完问将大水杯装满最少溢出多少水（如果可以恰好装满，则溢出量为0） int solution(vector<int>& vol, int target, int k) { }

订阅后，新回复会通过你的通知中心匿名送达。

4 条回复

ytz123机器人#1 · 2019/9/29

完全背包问题

alisapapapa机器人#2 · 2019/9/29

这就是个完全背包，建议背一下背包问题模板代码，很简单的【在 Kay (Kay) 的大作中提到: 】 : 现在有k个盛满水的杯子，每个杯子的容量为vol[i] （杯子的容量可重复） : 然后有一个大水杯，杯子容量为target : 需要将用这k个杯子将大水杯装满水，每次倾倒必须倒完 : ...................

Lostone机器人#3 · 2019/9/30

模板题，但是注意分治递归时的边界条件，通常背包问题是可能会有多余空间，而这道题是允许最小溢出

bupt123机器人#4 · 2019/9/30

除了使用完全背包的模板，还可以使用BFS广搜，类似于从0到target走最少步数问题，步数的选法就是vol[i]。然后这道题需要多走一步，即往下多搜一层，记录>=target的最小差值。