python: 最大積載量5000kgのトラックに700個の荷物を積むには何台のトラックが必要か。

講義でわからないのですが、以下の問をPythonを用いて答えを求めるコードを書いてください。



　ここに700個の荷物があり、それぞれの重さは1kg、2kg、3kg、……、700kgとなっています。これらを最大積載量5000kgのトラックを何台か使って運ぼうとしています。

　トラックに荷物を載せるのに、次のような方針を立てました。

　重い荷物から順にトラックに載せていく。
　ある荷物を載せると最大積載量を超えてしまう場合は、新しいトラックを用意してそちらに載せる。古いほうのトラックには以降は新しい荷物は載せない。

　この方針に従うと、

　1台目のトラックには700kg，699kg，698kg，697kg，696kg，695kg，694kgの荷物が載せられる。
　2台目のトラックには693kg，692kg，691kg，690kg，689kg，688kg，687kgの荷物が載せられる。

となります。最終的に何台のトラックが必要になるかを求めてください。

No.4 回答者： tknakamuri 回答日時： 2021/02/25 02:22

こんな簡単なロジックを人に頼んでたら

講義受けてる意味ないかな。

ここまで考えたけど、この先解らん

とか書かないと、回答者に対する敬意が無いと
みなされて、運営に消されてしまうよ。

No.3 回答者： cametan_42 回答日時： 2021/02/24 00:30

う〜ん、ゴメン。

バグ入れちゃってたや。

# ここから

def foo(m, n):
　lst = []
　s = []
　for i in range(m, 0, -1):
　　if sum(s) + i > n:
　　　lst += [s]
　　　s = []
　　s += [i]
　return lst + [s]

if __name__ == '__main__':
　print(len(foo(700, 5000)))

No.2 回答者： osamuy 回答日時： 2021/02/23 18:58

python使わなかったのでコードは略。

結果52台。
01台め 4879kg積 7個(700..694)
02台め 4830kg積 7個(693..687)
03台め 4781kg積 7個(686..680)
(snip)
50台め 4950kg積 36個(155..120)
51台め 4995kg積 54個(119..66)
52台め 2145kg積 65個(65..1)
Total=245350kg

ナップザック問題の変形で、DPで解けという問題かと思ったら違った。

No.1 回答者： cametan_42 回答日時： 2021/02/23 18:28

#!/usr/bin/env python3

def foo(m, n):
　lst = []
　s = 0
　for i in range(m, 0, -1):
　　s += i
　　if s > n:
　　　lst += [s - i]
　　　s = i
　return len(lst)

if __name__ == '__main__':
　print(foo(700, 5000))