이 광고는 무엇인가요? sci. prob. 전화 했어?

Question

몇 가지 실제 사용 사례에서이 문제를 생각했지만 어떤 정보인지 모르기 때문에 정보를 찾을 수 없습니다. 그것이 어떤 알려진 컴퓨터 과학 문제와 비슷하다면 다른 누군가가 아마 나보다 나은 해결책을했을 것입니다.

나는 다양한 종류의 벽돌을 포함하는 레고 더미가 있습니다. 특정 유형의 벽돌이 여러 개있을 수 있습니다. 나는 또한 일련의 디자인/레고로 만들 수있는 것들을 가지고 있는데, 각각 필요한 조각들의 목록을 가지고있다.

내 레고 더미로 무엇을 만들 수 있습니까? (한 번에 하나씩)

Answer 1

이것은 다차원 범위 쿼리 문제입니다. k가 벽돌 유형의 수이면 각 설계는 각 벽돌 유형의 필수 숫자 인 k- 차원 점 (길이 -k 배열)으로 나타낼 수 있습니다. 원하는 것은 집합입니다 힙에 해당하는 쿼리 포인트 (x_1, ..., x_k)의 해당 좌표보다 작은 좌표를 갖는 데이터베이스의 모든 포인트 중 하나를 선택합니다. 이것을 말하는 또 다른 방법은 (0, ..., 0) - (x_1, ..., x_k)로 묶인 hyperrectangle에서 점 집합을 찾는 것입니다.