E D R , A S I H C RSS
ZeroWiki

Knapsack

about

당신은 ZP κ³ΌμΌκ°€κ²Œ μ£ΌμΈμž…λ‹ˆλ‹€.

μ–΄λŠλ‚ , μ»€λ‹€λž€ μ£Όλ¨Έλ‹ˆλ₯Ό λ“  μ†λ‹˜μ΄ μ°Ύμ•„ μ™”μŠ΅λ‹ˆλ‹€. 그리고

"이 μ£Όλ¨Έλ‹ˆμ— 넣을 수 μžˆμ„ 만큼 과일을 λ‹΄μ•„ μ£Όμ„Έμš”."

μ΄λ ‡κ²Œ λ§ν–ˆμŠ΅λ‹ˆλ‹€. κ·ΈλŸ¬λ‚˜ μ£Όλ¨Έλ‹ˆμ˜ 곡간이 λ¬΄μ œν•œμ€ μ•„λ‹™λ‹ˆλ‹€.

당신이 λˆμ„ κ°€μž₯ 많이 λ°›κΈ° μœ„ν•΄μ„œλŠ” μ–΄λ–»κ²Œ ν•΄μ•Ό ν• κΉŒμš”?

예λ₯Ό λ“€μ–΄ 과일의 크기와 가격이 λ‹€μŒκ³Ό κ°™λ‹€κ³  ν•©μ‹œλ‹€.



과일크기가격
사과3800
λ°°41200
μˆ˜λ°•125000
μžλ‘1300
λ°”λ‚˜λ‚˜62000

μ—¬κΈ°μ„œ μ£Όλ¨Έλ‹ˆμ˜ 크기가 50이라고 ν•©μ‹œλ‹€.

μ–΄λ–»κ²Œ νŒ”μ•„μ•Ό κ°€μž₯ λ§Žμ€ λˆμ„ 벌 수 μžˆμ„κΉŒ?

그리고 κ·Έ λ•Œ λ²„λŠ” λˆμ€ μ–Όλ§ˆμΈμ§€ κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ„Έμš”.

(단, λ‹΄λŠ” μˆœμ„œλŠ” 관계 μ—†μŠ΅λ‹ˆλ‹€.)



specfication

μž…λ ₯ 예

50

사과 3 800

λ°° 4 1200

μˆ˜λ°• 12 5000

μžλ‘ 1 300

λ°”λ‚˜λ‚˜ 6 2000


좜λ ₯ 예

μˆ˜λ°• (12)을(λ₯Ό) λ‹΄μ•˜μŠ΅λ‹ˆλ‹€. 이제 남은 곡간은 38μž…λ‹ˆλ‹€.

μˆ˜λ°• (12)을(λ₯Ό) λ‹΄μ•˜μŠ΅λ‹ˆλ‹€. 이제 남은 곡간은 26μž…λ‹ˆλ‹€.

μˆ˜λ°• (12)을(λ₯Ό) λ‹΄μ•˜μŠ΅λ‹ˆλ‹€. 이제 남은 곡간은 14μž…λ‹ˆλ‹€.

μˆ˜λ°• (12)을(λ₯Ό) λ‹΄μ•˜μŠ΅λ‹ˆλ‹€. 이제 남은 곡간은 2μž…λ‹ˆλ‹€.

μžλ‘ (1)을(λ₯Ό) λ‹΄μ•˜μŠ΅λ‹ˆλ‹€. 이제 남은 곡간은 1μž…λ‹ˆλ‹€.

μžλ‘ (1)을(λ₯Ό) λ‹΄μ•˜μŠ΅λ‹ˆλ‹€. 이제 남은 곡간은 0μž…λ‹ˆλ‹€.

가격 = 20600

μ²˜μŒλΆ€ν„° 단박에 이 문제λ₯Ό ν‘ΈλŠ” 것보닀 쑰금 더 μ œν•œμ μ΄κ³  μ‰¬μš΄ λ¬Έμ œμ—μ„œ 일반적이고 μ–΄λ €μš΄ 문제둜 μ μ§„μ μœΌλ‘œ 진행해 λ‚˜κ°€λŠ” 것은 μ–΄λ–¨κΉŒμš”. NoSmok:HowToSolveItμ—μ„œ μ†Œκ°œν•˜λŠ” 문제 ν•΄κ²° ν…Œν¬λ‹‰ 쀑 ν•˜λ‚˜μ΄κΈ°λ„ ν•˜μ£ . 훨씬 더 높은 ꡐ윑적 효과λ₯Ό κΈ°λŒ€ν•  수 μžˆμ§€ μ•Šμ„κΉŒ ν•©λ‹ˆλ‹€.

μ˜ˆμ»¨λŒ€, λ‹€μŒμ˜ μˆœμ„œκ°€ κ°€λŠ₯ν•˜κ² μ£ :
  1. weighted, 0-1 knapsack problem -> find the exact match
  2. weighted, unbounded knapsack problem -> find the exact match
  3. weighted/valued, unbounded knapsack problem -> maximize the value not exceeding the weight limit

그리고 λˆ„κ΅°κ°€κ°€ λ§Œλ“  ν”„λ‘œκ·Έλž¨μ΄ μ˜³λ‹€λŠ” 것을 ν…ŒμŠ€νŠΈν•˜κΈ° μœ„ν•΄μ„œλŠ” 이λ₯Ό μžλ™ν™”ν•˜λŠ” 것이 νŽΈν•  것이고, 이것을 μœ„ν•΄μ„œλŠ” 인풋과 아웃풋을 μ’€ λ‹¨μˆœν™”ν•˜λŠ” 것이 쒋지 μ•Šμ„κΉŒ ν•©λ‹ˆλ‹€. ICPC의 λ¬Έμ œλ“€μ„ ꡬ경해 λ³΄μ„Έμš”.

--JuNe
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:36
Processing time 0.0172 sec