# Knapsack

joajy

1. Link https://www.acmicpc.net/problem/7579 비슷한 문제(평범한 배낭): https://www.acmicpc.net/problem/12865 2. 풀이 과정 > 1. N개 중 몇 개를 비활성화 하여 M바이트 이상을 확보하라 -> KnapSack problem(DP) 대학교 전공이 컴퓨터 계열이라면 아마 한 번쯤은 들어봤을 knapsack 문제입니다. 다만 저는 들은 지 오래돼서 우격다짐으로 코드를 작성했네요 ㅎ헣.. 암튼 간단하게 이야기하자면 우선 dp배열을 만든 근거는 row에서 N개의 앱을 파악하기 위해 100으로, column에서 N(<=100)개의 앱에 대한 cost(<=100)를 판단하기 위해 10000으로 설정했습니다. 이중 for문을 사용해 N개의 앱의 활성화, 비활성화 여부를 따집니다. 해당 칸이 받을 수 있는 값은 바로 위 칸의 값(활성화된 상태로 넘어감) 또는 위 행에서 cost만큼을 추가한 값(비

lifeisbeautiful

백준 29704번 https://www.acmicpc.net/problem/29704 문제 생각하기 배낭 문제이다. 메모이제이션을 활용해서 문제를 풀었다. 동작 배낭 문제의 대표적인 특징으로 선택하지 않고 통과, 선택 2가지만 잘 고려하면 된다. >memon = knapsack(n - 1, t) 이 선택하지 않는 부분이다. > 문제에서는 "

alsrl9165

https://www.acmicpc.net/problem/1535

lifeisbeautiful

백준 1535번 https://www.acmicpc.net/problem/1535 문제 생각하기 Knapsack 문제이다. DP를 통해서 최적화를 해야한다. 부르트포스도 가능(?)한 것 같다 TopDown재귀를 통해서 구현했다. 동작 배낭문제 특성을 이용해서 쉽게 풀 수 있다. 선택지가 크게 2개 배낭에

qazws78941

평범한 배낭 백준 12865 문제 링크 문제 > 이 문제는 아주 평범한 배낭에 관한 문제이다. > 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. > 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. 입력 > 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다.

baeyj1010

📌문제 📌코드 2차원 배열 1차원 배열 📌풀이 물건의 무게와 가치 2차원 배열 <br

tlagusejr

https://level.goorm.io/l/challenge/goormthon-challenge 통증 1문제는 a랑 b랑 서로 배수형태엿지만 해당 문제는 2 <= a,b <= 13 인 경우라서 다른 접근이 필요하다. dp라고 적혀있어서 단순 dp로 풀었지만 시간초과에 재귀 깊이 초과에 난리였따... 다른 방법이 있지 않을까 하다가 생각해 본 것은 순서가 상관 없다는 것이엿다 즉 a = 2 b = 5일경우 aaab 를 골른 결과랑 abaa baaa 다 같은결과이다.. 즉 냅색 문제와 관련 있을 것이라 생각햇다.. https://velog.io/@jxlhe46/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C-Knapsack-Problem 그래서 블로그를 참고해서 풀었는데 코드는 다음과 같다. 코드는 간단하다 -a 칸과 -b칸의 0과 1중에 최소값을 선택하고, -1이면 무시하는 코드이다..

kim_dong_jun99

아래 예시는 배낭 문제 알고리즘에 해당되는 대표적인 예시 중 하나이다. > 도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다. 각 보석들의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법은? 알고리즘 문제를 풀다가 위와 비슷한 상황을 직면한 적이 종종있었는데, 그럴때마다 풀릴 듯이 문제가 풀리지 않았어서 배낭 문제를 푸는 법에 대해서 한번 정리해보려고 한다. 위와 같은 문제를 직면할 때마다 들었던 생각은 가장 비싼 보석을 먼저 담으면서, 가방이 찢어지게되는 상황이 발생하면 가방에 있는 보석을 빼는 방식을 생각했었던 것 같은데, 반례가 존재하는 풀이인 것 같다. 위 문제는 dp를 이용해서 가장 효율적으로 풀이할 수 있다. 배낭 문제에서 사용되는 점화식은 아래와 같다. ![](https://img1.daumcdn.net/thumb/R1280x0/?scode=

seonydg

문제 출처: 백준 - 평범한 배낭 : 12865번 >### 풀이 DP(Dynamic Programming) Knapsack(냅색) 문제다. 냅색 문제는 2개의 짝을 이루는 값이 주어지는데 '무게, 가치', '시간, 가치', '넓이, 가치' 등이다. 이렇게 짝을 이룬 값이 주어질 때 이 값이 중복으로 사용할 수 있느냐 없느냐로 풀이가 조금 달라진다. 값이 여러개(무한)으로 주어질 때에는 중복을 허락하기에 가방 무게만큼의 1차원 배열에 순서대로 물건을 업데이트하며 중복으로 계산이 가능하다.([참고: 값이 무한일 때](https://velog.io/@seonydg/%EC%BD%94%ED%85%8C-%EC%95%8C%EA%B

seonydg

Knapsack 배낭(Knapsack) 혹은 가방 문제는 부분집합들 중 문제에서 제시하는 조건에 가장 알맞은(최적화) 부분집합을 찾는 문제다. 여기에선 그리디로 해결할 수 있는 'Fractional Knapsack Problem'처럼 짐을 쪼개는 문제가 아닌, 가방에 담을 수 있는 짐은 쪼개지 못하는 경우를 이야기한다. >그림출처:나무위키Knapsack 알고리즘 문제는 그림과 같이 가방 안에 무게를 초과하지 않으면서 담을 수 있는 최대한의 가치를 구하는 문제의 형태로 나타난다. 그래서 구할 수 있는 모든 부분집합 중에서 무게 15를 넘기지 않는 동시에

jeongbeom4693

Dynamic Programming DP중에서도 대표적인 문제로 꼽히는 문제가 있는데, 타일 채우기, 계단 오르기, 배낭 채우기등이 있습니다. 그 중 하나인 배낭 채우기(Knapsack Problem)을 알아보겠습니다. 먼저 문제의 유형을 이해하기 위해서 예시를 통해서 살펴보겠습니다. 다음은 백준 12865번: 평범한 배낭 문제 입니다. 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이

asmka2

백준 7579번 링크 Knapsack problem Optimization version NP hard 문제이다. Optimization version의 정의는 다음과 같다. Input: Positive integers $$W, w{1}, ... , w{n}$$ and $$v{1}, ... , v{n}$$ Output: A subset S $$\subset$$ {1, ... , n} that maximizes $$\Sigma{i\in S}v{i}$$ subject to $$\Sigma{i\in S}w{i} \le W$$ 쉽게 말하면 n개의 배낭이 있고, 각 배낭은 가격과 가치가 있다. 한정된 돈으로 최대한의 가치를 얻는 방법을 묻는 문제다. weight와 value라고 표현하는 게 개인적으로 편한 것 같다. Deicision version 이 문제가 NP hard인 것을

ycw92325

N개의 문제를 풀수 있다. 제한 시간 M에서 얻을 수 있는 최대점수를 구하라. 첫번째 줄에 N과 M입력 두번째줄 부터 문제 풀었을때 얻는 점수와 시간 ex) 5 20 10 5 25 12 15 8 6 3 7 4 출력) 최대점수 41

ycw92325

거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게주면되는가 입력) 첫째 줄에 동전의 종류개수 N 두번째 줄에는 N개 동전의 종류 마지막 줄에 거슬러줄 금액 M ex) 3 1 2 5 15 출력) 거슬러줄 동전의 최소의 개수를 출력 3

beberiche

문제 풀이 요약 냅색 문제. 풀이 상세 최대무게인 $K$ 부터 시작하여, 현재 무게와 아이템 무게를 비교한다. 만약 임의의 가방 무게 $Kj$ 에서 가져올 수 있는 $dp$ 값이 존재한다고 하자. 만약 다음 아이템의 무게를 구하는 중, 현재 가방의 무게를 뺐을 때 임의의 가방 무게 $Kj$ 의 $dp$ 값에 도달한다면 이는 현재 가방 무게에서 두 아이템의 가칫값을 더하는 것이 가능하다는 것을 의미한다. 정답

wlstkd5129

[문제] 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. [입력] 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다.

1ong1ong

1. Knapsack 문제란? > 물건에는 무게와 가치가 있고, > 그러한 물건이 여러가지가 주어졌을 때, > 배낭의 용량이 정해져있다면 > 배낭에 담을 수 있는 물건의 최대 가치는 얼마인지 찾는 문제 2. DP를 이용할 수 있는 이유 물건을 가져갈 수 있는 선택지를 1부터 하나씩 증가시키고, 배낭에 담을 수 있는 물건의 최대 가치도 1부터 하나씩 증가시킨다면, 앞에서 구한 작은 문제들의 해를 가지고 다음 문제의 해를 구할 수 있습니다. 3. DP를 이용해 풀어보기 i 번째 물건을 가져갈 수 있는 선택지가 생겼을 때, (knapsack\[i]\[배낭에 담을 수 있는 최대 가치 j]) 다음 두 가지 방법이 생깁니다. i를 가져가는 경우, 전체 가치는 물건 i의 가치 + knapsack\[i - 1]\[j - 물건 i의 무게]와 knapsack\[i-1]\[j] 중 최대값이 됩니다. i를 가져가지 않는 경우, 전체 가치는 knap

na0ngkim

배낭 문제(knapsack probrem)는 DP 문제의 일종이다. 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제이다. 대표적인 문제는 이 문제라고 생각한다. https://www.acmicpc.net/problem/12865 문제 > 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수

kylebae1017

Greedy vs. DP 작년 알고리즘 수업에서 Greedy Algorithm과 Dynamic Programming의 공통점과 차이점에 대해서 공부했었다. 너무나도 유명하고 굉장히 자주 쓰이는 이 두 알고리즘 계획법은 언뜻 보면 별로 다르지 않은 것 같아도 차이점이 분명히 있다. 두 알고리즘 계획법이 비슷해보이는 이유는 두 계획법 모두 다 optimal substructure를 사용하기 때문이다. 여기서 optimal substructure라는 것은, 어떠한 문제에 대한 optimal solution이 그 문제의 subproblem에 대한 optimal solution을 포함하고 있다는 것이다. 하지만 DP에서는 (일반적으로) bottom-up 방식으로 작은 subproblem에서부터 solution 탐색을 진행하고, 그리디는 solution을 찾는 과정에서 그 순간 가장 효율적인 선택을 진행한다는 점에서 차이가 있다. **그렇기 때문에 DP로 풀리는 문제가 그

ppparkta

12865 평범한 배낭 배낭문제라는 문제유형을 알아야 한다. 배낭의 용적 가능 무게가 k일 때 n개의 물건(각 물건에는 w:무게, v:가치가 존재함)이 존재한다면 배낭에 담을 수 있는 물건의 최대 가치는 몇인지 구하는 문제이다. dp를 사용하지만 처음 접하는 문제이기 때문에 풀이를 자세하게 적어보려고 한다. 문제의 예제로 설명해보겠다. w|v ::-::|::-:: 6|13 4|8 3|6 5|12 이런 표가 있을 때 최대 가치를 구하기 위해서 배낭에 수납할 수 있는 무게가 1부터 k일 때의 모든 최대가치를 구하려고 한다. 물건번호(i) \ 최대무게(k)|k=1|k=2|k=3|k=4