부분적 배낭 문제(the fractional knapsack problem)1 [ps java] BOJ 12865 평범한 배낭 해설 웰-노운 배낭(냅색) 문제이다 [골드5]https://www.acmicpc.net/problem/12865 [부분적 배낭 문제(the fractional knapsack problem)] - 각 항목의 일부만을 취할 수 있는 문제흔히 ps에서 "냅색"이라 말한다 구성: n항목의 집합 S- bi: 양수의 이득- vi: 양수의 부피목표: 최대 부피 한도 V내에서, 최대의 총이득을 주는 항목들을 선택32 + 15 = 47 0-1 배낭 문제(all-or-nothing knapsack problem) - 각 항목의 일부만을 취할 수 없는 문제0-1 배낭 문제는 탐욕적 선택 속성을 만족하지 않는다 >> DP로 해결 최적해는 이득 = 36 을 가져다주는 {A, E}지만, 탐욕해는 이득 = 24 를 가져다주는 {B.. 2025. 3. 18. 이전 1 다음
