[Java] Knapsack
1. Knapsack Knapsack 문제는 조합 최적화 문제의 일종으로 주어진 물건들의 가치와 무게, 그리고 배낭의 총용량이 주어졌을 때, 배낭에 넣은 물건들의 가치의 합이 최대가 되도록 하는 물건들의 부분집합을 찾는 문제이다. 동적 계획법(Dynamic Programming)으로 풀 수 있다. 0-1 Knapsack: 각 물건을 배낭에 넣거나 넣지 않거나 두 가지 경우만 고려하는 문제.0-N Knapsack: 각 물건을 배낭에 여러 개 넣을 수 있는 문제입니다.Fractional Knapsack: 각 물건을 배낭에 일부분만 넣을 수 있는 문제입니다.: 무게 대비 가치가 높은 물건부터 배낭에 담는 탐욕 알고리즘(Greedy Algorithm)을 이용하여 풀 수 있다. import java.io.Buf..
2024.06.12