티스토리 뷰
https://www.acmicpc.net/problem/12865
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
동적계획법 C++
2020 하계 방학 알고리즘 스터디의 마지막을 장식할 DP 문제 knapsack 문제다!!!
문제는 설명하기 입아프니 위 사진을 참고하도록 하시고
이번 여름방학 스터디 마지막 문제로 knapsack 문제를 정석으로 코드를 짜보려고
이 문제를 골랐다.
접근방법
상향식 접근, 최적의 원리 등의 접근으로 풀이하는 대표적인 DP문제 중 하나인 knapsack(배낭채우기 0-1)문제
0-1이 아니면 그리디로 풀이하면 되지만 0-1은 DP로 풀이해야한다.
하지만 knapsack을 DP로 풀이한 아래 풀이법은 시간복잡도가 O(NW)이다.
배낭에 담을 수 있는 무게가 너무 커지면 이것도 N^2이상의 복잡도를 갖는다. (NP문제)
갖고있는 물건의 개수 만큼의 행을 갖고, 배낭에 담을 수 있는 무게의 범위 만큼의 열을 갖는 이차원 배열을 사용한다.
배열에 저장되는 값은 이렇다. (행 : i, 열 : w) i까지의 물건을 w무게 만큼 넣을 수 있다고 할때 가장 큰 가치를 저장한다.
이때 i번째 물건을 넣지 않았을 때와 i번째 물건을 넣을 공간을 마련한 후 i번째 물건을 넣었을 때의 배낭에 든 물건의 가치를 비교한다.
이때 추가로 처리하는 것은 w무게 보다 i번째 물건의 무게가 클때 이때는 i번째 물건을 넣지 않았을 때의 경우와 같은 값을 저장한다.
소스코드
#include <iostream>
using namespace std;
int dp[101][100001];
int main(){
int n, k;
cin >> n >> k;
int weight, worth;
for(int i = 1 ; i <= n ; i++){
cin >> weight >> worth;
for(int w = 0 ; w <= k ; w++){
if(weight > w || (worth+dp[i-1][w-weight] < dp[i-1][w]) )
dp[i][w] = dp[i-1][w];
else
dp[i][w] = dp[i-1][w-weight] + worth;
}
}
cout << dp[n][k];
return 0;
}
'알고리즘 문제풀이' 카테고리의 다른 글
[백준 1654]알고리즘 55일차 : 랜선 자르기 (0) | 2020.12.29 |
---|---|
[백준 10816] 알고리즘 54일차 : 숫자 카드 2 (0) | 2020.12.28 |
[백준 11057] 알고리즘 52일차 : 오르막 수 (0) | 2020.08.27 |
[백준 11054] 알고리즘 51일차 : 가장 긴 바이토닉 부분 수열 (0) | 2020.08.26 |
[백준 9095] 알고리즘 50일차 : 1,2,3더하기 (0) | 2020.08.25 |
- Total
- Today
- Yesterday
- Swift
- dfs
- 게임이론
- 트리
- 토마토
- 백준
- 우선순위큐
- 투포인터
- 그리디알고리즘
- 웹크롤링
- 정렬
- 이분탐색
- c++
- 최단경로
- 최소힙
- 프로그래머스
- 최대힙
- 가장 큰 수 Swift
- 알고리즘
- 스택
- 백트래킹
- 수학
- 동적계획법
- 파이썬
- 다이나믹프로그래밍
- dp
- 브루트포스
- BFS
- 가장 큰 수 프로그래머스
- 자바
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |