去楼下超市买东西发现个活动，满 18 送可乐一瓶，发现有点意思

[loverorser]

小明去超市买东西，超市有一个活动。商品一件一件结算后，消费每满 18 元赠送可乐一瓶。但是超市的机器太老旧了，每次结算最多只能给一瓶可乐，想要获得多瓶可乐就要分开结算。
小明想知道如何结算才能获得尽可能多的可乐。
输入，一个正整数 N （ 0<N<100000 ），表示小明买了多少件商品
N 个正整数 A （ 0<A<1000 ），表示每件商品的价格
一个正整数 M(0<M<100 ），表示每满多少给一瓶可乐
输出，可能获得可乐的最大数量。

[AoEiuV020JP]

这种 acm 级别的题目应该是现在思考型 AI 攻克的重点吧，不知道能不能解决了， 我做这种是挺头疼的，

[Yuanlaoer]

这不就是背包（ DP ）么

[summerwar]

最优化问题

[hefish]

动态规划嘛，数据结构里有例题，照着写一下。

[witfun]

@AoEiuV020JP 我尝试问了下 deepseek ，😐

[lrjia]

把 M 设成所有正整数和的一半就是分区问题了

[alect]

最大应该是总金额除以 M 余下的整数解。