1. 전제. 가장 큰 입금 계좌를 최대로 채울 수 있는 방법이 언제나 옳음.
10만큼 채울 수 있는 계좌를 먼저 최대로 채운 후에 진행하는게, 9인 계좌를 먼저 최대로 채우는 것보다 언제나 많이 채울수 있음.
2. n만큼 채울 수 있는 계좌에 x1, x2, x3등 값이 있을 때, 최대로 채우는 방법은 이미 널리 알려저있음. 동적계획법 쓰면 됨
3. 가장 입금 금액 큰 계좌부터 작은 계좌 순으로 백팩 풀면 됨. 큰 입금 계좌에 입금하지 않은 금액만 남겨서 다시 작은 계좌로 백팩
백팩이 아니라 배낭. 난 왜 자꾸 Knapsack를 백팩이라고 읽는지 모르겠는데 어쨌던...
아, 계좌에 입금하는 금액도 규칙 있어야되네 잠깐 고민좀 해보고...
입금 금액이 4,5,7,2일 경우. 입금 계좌가 9, 2이면 9인 계좌에는 4,5를 입금해야 최대가 되고, 입금 계좌가 9, 4이면 9인 계좌에 7,2를 입금해야 최적이 됨. 9인 계좌 계산하는 시점에서 뭐가 최적인지 어떻게 계산할지 모르겠다. 일단 씻으려다가 문제 봐서 못씻고 있던지라 샤워 하고 고민해봄.
ㄴ 이 경우엔 또 2나 4를 먼저 채워야 하네요...
거꾸로 작은 계좌를 먼저 채우는게 항상 옳은건가??
작은 계좌부터 채우는게 틀린 반례 하나 만들어줄수 있어?? 뭔가 증명이 잘 안되는데
작은 계좌 최대로 채우고 남은 애들 가지고 채우는게 맞는거 같아.
나도 해봤는데 큰것부터가 맞는거 같은데,
N=4, i=500, ea=8 450 200 240 300 470 220 100 80
아 그러네. 계좌 크기가 다 같구나 ㅋㅋㅋㅋㅋ 이제 알았음 그냥 백팩 몇번 하셈
괜히 고민했네 1번 빼고 2,3번 그냥 하면 됨. 만약 계좌 금액이 다 다르다면 작은 계좌부터 최대로 채우는게 답인거 같음. 작은 계좌를 먼저 최대로 채우는게 단편화를 최소화 하는 방법임.
아니 이게 작은것부터 할때 큰게 있고, 큰것부터 할때 큰것이 있고, 그러네