上个月开始税改了,餐饮报销的发票只能是增值税发票。也就是说,以前的5元,10元的手撕发票都用不了了。这个月开始的所有能报的发票都是增值税发票,也就是金额可能很大,但是费用都很随机的数。整理发票发现我总共的能报的发票总共有10张,总值是2000多,而我这个月的可报上限是1330. 那么还剩600多是可以留到下个月去报的。
这个时候就出现了一个问题,我怎么报才能使我报的金额能报满上限,并且总和最小,同时留下的发票金额总和是最大的呢?
把问题抽象出来就是:
总共有N个数,分别为a1, a2, … aN, 现在有一个数m,我选取N个数中的n个数(n <= N), 使得sum(选中的n个数) >= m, 并且剩余的(N-n)个数的总和最大?
举个例子:
10个数:
22, 93, 120, 237, 242, 267, 317, 374, 435, 477.
特殊的数m: 1330
应该选10个数中的那几个数求和才能大于1330, 并且剩余数的和最大呢?