์ด ๊ณ์ฐ๊ธฐ๋ก ํ ์ ์๋ ์ผ
๋ฐ๋ฒจ ์ํ ๊ณ์ฐ๊ธฐ๋ ๋ชฉํ ์ค๋์ ๋ง์ถ๊ธฐ ์ํด ๋ฐ๋ฒจ ์์ชฝ์ ์ด๋ค ์ํ์ ๋ผ์์ผ ํ๋์ง ์ ํํ ์๋ ค์ค๋๋ค. ์ธํธ ์ฌ์ด๋ง๋ค ๋จธ๋ฆฟ์์ผ๋ก ๋ฌด๊ฒ๋ฅผ ๊ณ์ฐํ ํ์ ์์ด, ๋ชฉํ ์ค๋๊ณผ ๋ฐ(๋ด) ๋ฌด๊ฒ๋ง ์ ๋ ฅํ๋ฉด ํ์ด๋(lb) ๋๋ ํฌ๋ก๊ทธ๋จ(kg) ๋จ์๋ก ํ์ชฝ์ ๋ผ์ธ ์ํ ์กฐํฉ์ ์ฆ์ ํ์ธํ ์ ์์ต๋๋ค.
์ฌ์ฉ ๋ฐฉ๋ฒ
๋จผ์ ๋จ์(lb ๋๋ kg)๋ฅผ ๊ณ ๋ฅด๊ณ , ๋ชฉํ ์ด์ค๋์ ์ ๋ ฅํ์ธ์(์: 225 lb). ๊ทธ๋ค์ ๋ฐ ๋ฌด๊ฒ๋ฅผ ์ ๋ ฅํฉ๋๋ค(ํ์ค ์ฌ๋ฆผํฝ ๋ฐ๋ 45 lb ๋๋ 20 kg). ๊ณ์ฐ๊ธฐ๋ ์ ์ฒด ๋ฌด๊ฒ์์ ๋ฐ ๋ฌด๊ฒ๋ฅผ ๋บ ๋ค ๋จ์ ๋ฌด๊ฒ๋ฅผ ์์ชฝ์ ๋๊ฐ์ด ๋๋๊ณ , ํ์ค ์ํ ์ค์์ ๊ฐ์ฅ ์ ์ ๊ฐ์๋ก ํ์ชฝ ๋ฌด๊ฒ๋ฅผ ๊ตฌ์ฑํฉ๋๋ค.
๊ณ์ฐ ๊ณต์ ํ์ด
๋จผ์ ํ์ชฝ์ ๋ค์ด๊ฐ์ผ ํ ๋ฌด๊ฒ๋ฅผ ๊ตฌํฉ๋๋ค: $$P = \dfrac{\text{๋ชฉํ ์ค๋} - \text{๋ฐ ๋ฌด๊ฒ}}{2}$$. ๊ทธ๋ฐ ๋ค์ ํ์(greedy) ๋ฐฉ์์ผ๋ก ๋ฌด๊ฒ๋ฅผ ๋ถํดํ๋๋ฐ, ๋ผ์ธ ์ ์๋ ๊ฐ์ฅ ํฐ ์ํ๋ถํฐ ์ฐจ๋ก๋ก ๊ณจ๋ผ ํ์ชฝ์ ์ฑ์ ๋๊ฐ๋๋ค. ํ์ด๋ ์ํ์ \(45, 35, 25, 10, 5, 2.5\) lb๋ฅผ ์ฌ์ฉํ๊ณ , ํฌ๋ก๊ทธ๋จ ์ํ์ \(25, 20, 15, 10, 5, 2.5, 1.25, 0.5\) kg๋ฅผ ์ฌ์ฉํฉ๋๋ค. ๋ณด์ ํ ์ํ์ผ๋ก ์ ํํ ๋ง์ถ ์ ์๋ ๋ฌด๊ฒ๋ "๋จ๋ ๋ฌด๊ฒ(๋ง์ถ์ง ๋ชปํ ์ฐจ์ด)"๋ก ํ์๋ฉ๋๋ค.
์์๋ก ๋ณด๋ ๊ณ์ฐ
45 lb ๋ฐ์์ ๋ชฉํ ์ค๋์ด 225 lb์ธ ๊ฒฝ์ฐ: $$\frac{225 - 45}{2} = 90 \text{ lb (ํ์ชฝ์)}$$ ํ์ ๋ฐฉ์์ผ๋ก ์ฑ์ฐ๋ฉด \(45 \times 2 = 90\) lb์ด๋ฏ๋ก, ์์ชฝ ๋์ ๊ฐ๊ฐ "45 lb ร 2"๋ฅผ ๋ผ์ฐ๋ฉด ๋ฉ๋๋ค. ์ค์ ์ด์ค๋์ \(45 + 180 = 225\) lb๋ก ๋ฑ ๋ง์๋จ์ด์ง๋ฉฐ ๋จ๋ ๋ฌด๊ฒ๋ ์์ต๋๋ค.
์์ฃผ ๋ฌป๋ ์ง๋ฌธ
๋ชฉํ ์ค๋์ ์ ํํ ๋ง์ถ ์ ์๋ ์ด์ ๋ ๋ฌด์์ธ๊ฐ์? ํ์ชฝ ๋ฌด๊ฒ๊ฐ ๋ณด์ ํ ์ํ๋ค์ ํฉ์ผ๋ก ๋ฑ ๋จ์ด์ง์ง ์์ผ๋ฉด(์: 0.5ํ์ด๋ ๊ฐ์ ์ด์ค๊ฐํ ๊ฐ), ๊ณ์ฐ๊ธฐ๋ ๋ผ์ธ ์ ์๋ ๊ฐ์ฅ ๊ฐ๊น์ด ๋ฌด๊ฒ์ ๋จ๋ ์ฐจ์ด๋ฅผ ํจ๊ป ๋ณด์ฌ์ค๋๋ค.
๋ฐ ๋ฌด๊ฒ๋ ์ผ๋ง๋ก ์ค์ ํด์ผ ํ๋์? ํ์ค ๋จ์ฑ์ฉ ์ฌ๋ฆผํฝ ๋ฐ๋ฒจ์ 45 lb(20 kg), ์ฌ์ฑ์ฉ ๋ฐ๋ 35 lb(15 kg)์ ๋๋ค. ํธ๋ ์ด๋ ๋ฐ๋ ๋ฌด๊ฒ๊ฐ ๋ค์ํ๋, ์ค์ ๋ก ์ฌ์ฉํ๋ ๋ฐ์ ๋ฌด๊ฒ๋ฅผ ์ ๋ ฅํ์ธ์.
์ํ ๊ฐ์๋ ํ์ชฝ ๊ธฐ์ค์ธ๊ฐ์, ์ ์ฒด ๊ธฐ์ค์ธ๊ฐ์? ํ์๋๋ ์กฐํฉ๊ณผ ๋ฌด๊ฒ๋ ๋ชจ๋ 'ํ์ชฝ' ๊ธฐ์ค์ ๋๋ค. ์์ชฝ ๋์ ๋์ผํ๊ฒ ๋ผ์ฐ๋ฉด ๋ฉ๋๋ค.