목록알고리즘/Knapsack Problem (가방문제) (2)

프로그래밍에 대한 고찰 및 생각

[2][Knapsack][0/1 배낭 문제] (0/1Knapsack Problem)

배낭 문제 배낭문제는 n개의물건이 있고 각각 무게와 가치가 주어질때, 물건을 m이하의 무게로 담을때 가능한 최대 가치를 구하는 문제이다. 이 배낭 문제는 크게 3가지로 분류된다. 배낭 빈틈없이 채우기 문제 ( Fractional Knapsack Problem) 0/1 배낭 문제 (0/1 Knapsack Problem) 개수제한 없는 0/1 배낭 문제 (Unbounded Knapsack Problem) 이 중 0/1 배낭 문제 (0/1 knapsack problem) 에 대해 알아보자. 0/1 배낭 문제 ( 0/1 Knapsack Problem) 0/1배낭 문제는 최대 가방무게 이하로 물건을 담을때 가치가 최대로 최게 담아야하는데 단, 물건을 일부만 담을 수 없고 담거나 담지 않거나 둘중 한가지를 택해야한..
알고리즘/Knapsack Problem (가방문제) 2020. 3. 4. 21:34
[1][Knapsack][배낭 빈틈없이 채우기 문제] (Fractional Knapsack Problem)

배낭 문제 배낭문제는 n개의물건이 있고 각각 무게와 가치가 주어질때, 물건을 m이하의 무게로 담을때 가능한 최대 가치를 구하는 문제이다. 이 배낭 문제는 크게 3가지로 분류된다. 배낭 빈틈없이 채우기 문제 ( Fractional Knapsack Problem) 0/1 배낭 문제 (0/1 Knapsack Problem) 개수제한 없는 0/1 배낭 문제 (Unbounded Knapsack Problem) 이 중 배낭을 빈틈없이 채우는 문제에 대해 알아보자. Fraction Knapsack Problem 배낭 빈틈없이 채우기 문제는 최대 가방무게 이하로 물건을 담을때 가치가 최대로 최게 담아야하는데 단, 물건을 일부만 담을 수도 있다. 예를 들어 무게가 10이고 가치가 20인 물건 A를 절반만 담으면 무게가 ..
알고리즘/Knapsack Problem (가방문제) 2020. 3. 3. 22:26
이전 Prev 1 Next 다음