제한된 리소스에 대해 경쟁하는 소비자 컬렉션이 주어지면 적용 가능성을 극대화하기 위해 리소스를 할당하십시오.

Question

죄송합니다. 제목이 명확하지 않으므로보다 구체적인 예를 제시하지 않고 질문하는 것이 좋습니다. 다음 시나리오를 고려하십시오.

저는 생일에 생일 (d1..dn)이오고있는 친구가 몇 명 있는데, 그 중 몇 명을 사야겠습니까? 비용 (c1..cn). 불행히도, 나는이 선물을 구입할 때 하루에 저장할 수있는 고정 금액 (m) 만 가지고 있습니다. 내가 물어보고 싶은 질문은 다음과 같습니다.

내 친구 사이의 합계 편차를 최소화하기 위해 선물 (예 : mi, 1.11.n == m의 합계) 당 절약의 이상적인 분배 란 무엇입니까? '생일과 그 선물을 사기에 충분한 돈을 저축 할 날짜.

내가 찾고있는 것은이 문제에 대한 해결책이거나 결정 론적으로이 질문에 답하기 위해 활용할 수있는 해결 된 문제에 대한 매핑입니다. 숙고 해 주셔서 감사 드리며 추가 설명을 제공해 드릴 수 있는지 알려 주시기 바랍니다.

Answer 1

배낭 문제가 NP 합병 (p247, Garey and Johnson)인데, 몇 가지 추가 합병증이있는 배낭 문제가 있다고 생각합니다. 기본 배낭 문제는 볼륨과 값이 각각있는 여러 개의 개체가있는 곳입니다. 배낭의 용량을 초과하지 않고 값을 최대화하기 위해 개체와 함께 고정 된 볼륨의 배낭을 채우고 싶습니다.

구매할 항목을 결정하는 동안 스테이지 (일) 및 리소스 (돈)가 있고 하루에 리소스가 변경되면 직선 최적화 모델이 아닌 동적 프로그래밍 솔루션 기술로 연결됩니다.

'편차 최소화'의견에서 명확히 설명해 주시겠습니까? 그 부분을 잘 모르겠다.

현재로서는 mathoverflow.com이 도움이되지 않습니다. 알고리즘 질문, stackoverflow 50 및 mathoverflow 50 살펴보면 stackoverflow에 대한 질문 및 대답을 당신이 고려하는 문제가 훨씬 더 공통점을 찾을 수 있습니다. OR Exchange라는 새로운 사이트가 있지만 아직 트래픽이 많지 않습니다.