글 읽기 - 현실 생활에서의 알고리즘 질문

baramhint 4년 전 1

회사에서 쓰는 식권 앱이 있는데

1일 1결제밖에 안되는 시스템입니다.

예를 들어 8명의 인원이 잔액이 아래 처럼 남아 있고,

10500, 22000,7600,2000,30000,5500,7700,8400

현재 음식점에서 48000원을 결제해야 한다고 쳤을때 가장 큰 금액을 남길 수 있는 방법을 구할려고 하는데요.

이경우 30000+10500+5500+2000으로 결제했을 때 가장 효율적이죠 남은 금액은 다른곳에서 쓸 수 있으니
그리디 알고리즘으로는 해결이 안될 것 같고..
제가 생각한 방법은 8명의 잔액 총합 - 목표 금액 (93700 - 48000) = 457에 가장 가까운 조합을 구하려고 하는데
혹시 무엇을 검색해보면 해당 알고리즘 같은게 있을까요?

startlink 4년 전 1

다이나믹 아닐까요

isku 4년 전 1

안녕하세요.

1인당 1결제이니, 결제할 사람을 최소로 선택해야 남은 인원이 결제를 할 수 있겠군요.

이 문제의 경우에는 네트워크 플로우 문제로 풀 수 있을 것 같습니다.

u에서 v로 가는 edge의 capacity는 그 사람이 가지고 있는 금액이고, 어떤 사람을 선택하는지를 나타내는 cost를 1로 구성하면, 이분 그래프의 형태가 될 것입니다.

source에서 sink로 총 결제 금액을 유량으로 흘릴 때, cost를 최소로 해야하는 문제가 될 것 같고,

이는 MCMF (minimum cost, maixmum flow) 문제입니다.

저는 아직 초보라 틀릴 수도 있습니다. 밑에 더 갓 분들이 자세하게 알려주실 거에요~

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

현실 생활에서의 알고리즘 질문

baramhint 4년 전 1

startlink 4년 전 1

isku 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말