Knapsack Problem(DP)-알고리즘11

Knapsack Problem(배낭채우기 문제) 배낭채우기 문제는 최대용량 w를 가지는 배낭에 각각 다른 값어치,무게를 가지는 물건들을 넣을 때, 총 값어치(배낭에 넣은 물건들의 값어치의 합)가 최대가 되도록 물건들을 골라서 넣는 경우를 찾는 문제이다. 배낭에 책을 담으려고 한다. 배낭의 최대 용량은 W이며, 이를 초과해서 책을 담으면 배낭이 찢어질 것이다.각 책의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 책을 담는 방법은? knapsack problem 에는 두가지 버전이 있다. 0-1 Knapsack problem :배낭에 물건을 담거나, 안담거나. -Dynamic Programming 을 사용한다. Fractional Knapsack Problem: 배낭에 물..

2023.08.30