1202번 - 보석 도둑
NP가 무엇인가요..?
계산 이론에서 문제를 분류할 때, 다항함수에 비례하는 시간 복잡도의 알고리즘으로 정답을 구할 수 있는 문제를 P 문제라고 하고, 다항함수에 비례하는 시간 복잡도의 알고리즘으로 어떤 답이 정답인지 아닌지 확인할 수 있는 문제를 NP 문제라고 합니다. 정의상 모든 P 문제는 NP 문제이지만 그 중 극소수에 불과하고, NP 문제의 대다수는 다항시간 복잡도로 정답을 구하는 알고리즘이 발견되지 않았습니다. 외판원 순회, 배낭 문제, 작업 스케줄링 모두 일반적인 조건에서 NP 문제입니다.
댓글을 작성하려면 로그인해야 합니다.
ckdgusjang 2년 전 1
1202에 대한 질문은 아니지만 궁금한 것이 생겨서 올립니다.
1202문제에서는 배낭 1개당 1개의 보석만을 넣는것으로 되어있습니다.
만약 1개의 배낭에 1개의 보석으로 제한되어있지않다면 어떻게 풀이해야할가요..?
1개의 배낭에 여러개의 보석을 넣을 수 있고 이때 배낭에 넣은 보석들은 다른 배낭에 못넣는다고 가정하면 최대 넣을 수 있는 무게는 어떻게 구해야 할가요?