n개의 볼과 m개의 빈이 주어지고 각 빈이 특정 용량을 가질 때, 몇 개의 조합이 있습니까? (Given n balls and m bins, each bin with a certain capacity, how many combinations are there?)

문제 설명

n개의 볼과 m개의 빈이 주어지고 각 빈이 특정 용량을 가질 때, 몇 개의 조합이 있습니까? (Given n balls and m bins, each bin with a certain capacity, how many combinations are there?)

n개의 동일한 볼과 m개의 고유한 빈이 주어지고 각 빈은 특정 용량(0에서 z까지, 여기서 z는 15보다 작거나 같은 음이 아닌 정수)을 가질 때 분배하는 방법에는 몇 가지가 있습니까? 불알? 이러한 유형의 문제를 해결하기 위한 범용 알고리즘이 있습니까?

나는 "별과 막대"를 발견했습니다. 및 "포함/제외"; 원칙이지만 여기 stackoverflow에서 몇 가지 질문/답변을 찾았지만 어떤 대답도 n의 임의 크기로 확장할 수 있을 만큼 충분히 일반적이지 않은 것 같습니다. 이를 해결하는 한 가지 방법은 동적 프로그래밍을 사용하는 것 같습니다. 임의의 n에 대해 이것이 어떻게 수행될 수 있습니까(아래 솔루션의 문제는 Python에서 n = 1000과 같이 상대적으로 작은 n에 대해 재귀 깊이가 너무 커지는 것입니다).

tmpquestionwonderer7777272、David Eisenstat)

참조 문서

1. Given n balls and m bins, each bin with a certain capacity, how many combinations are there? (CC BY‑SA 2.5/3.0/4.0)