Knapsack Problem
Coddy의 재귀 챌린지 - 재귀적 사고 마스터하기 코스 레슨 — 15개 중 7번째.
챌린지
중급배낭 문제(knapsack problem)는 매우 유명한 문제입니다.
이 문제에서 당신은 담을 수 있는 무게가 미리 정해진 배낭(knapsack)과 각각 무게와 가치를 가진 아이템들(items)을 가지고 있습니다.
당신의 작업은 배낭의 무게 제한 내에서 최대한 많은 가치를 담는 것입니다.
예를 들어,
values - [20, 5, 40, 10, 15]
weights - [1, 2, 8, 3, 7]
배낭의 무게(Weight of knapsack) - 10
해결책은 무게가 1과 8이고 가치가 20과 40인 아이템을 선택하는 것입니다.
최대 가치는 60이며, 총 무게는 9입니다(이는 10보다 작거나 같으므로 유효한 무게입니다).
정수 W와 두 개의 정수 배열 values 및 weights를 입력받아, 입력된 값들을 사용하여 배낭 문제의 해답(배낭에 담을 수 있는 최대 가치)을 반환하는 knapsack이라는 이름의 함수를 작성하세요.
직접 해보기
#include <stdio.h>
#include <stdlib.h>
int knapsack(int W, int* values, int values_size, int* weights, int weights_size) {
// 여기에 코드를 작성하세요
return 0;
}
재귀 챌린지 - 재귀적 사고 마스터하기의 모든 레슨
2Medium Challenges
Knapsack ProblemNumber of SquaresInterleaving ResultSum CombinationsFind TripletSplit Array