12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
1. 풀이방법
- 처음에 떠올린 방법은 브루트 포스로 모든 경우의 수 (조합) 을 모두 계산해 보는 것
- 이렇게 짜볼까 하다가 시간초과가 매우 발생할 것 같아서 방향을 바꿨습니다.
- 그냥 메모리를 사용해서 버틸 수 있는 무게 별로 최대가치를 저장하는 테이블을 선언하자 라고 생각.
- N개의 물건들을 하나씩 살펴 보면서 버틸 수 있는 무게 K 밑으로 살펴보며 이 물건을 넣어가며 테이블을 갱신
2. 주의사항
- 아직 알고리즘 문제풀이가 많이 부족해서 기존의 떠오른 생각 방향에서 다른 쪽으로 생각하는게 부족...
- 열심히 풀어야겠습니다...
3. 나의코드
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int N, K;
int dp[100001]; // 버틸 수 있는 무게 별로 최대가치를 저장하는 테이블
int weightarr[101];
int valuearr[101];
void dypro() {
for (int i = 1; i <= N; i++) {
for (int j =K; j >= 0; j--) {
if (weightarr[i]<= j) {
dp[j] = max(dp[j], dp[j- weightarr[i]] + valuearr[i]);
}
}
}
cout << dp[K] << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> K;
for (int i = 1; i <= N; i++) {
cin >> weightarr[i] >> valuearr[i];
}
dypro();
return 0;
}'알고리즘 문제풀이 > 다이나믹 프로그래밍' 카테고리의 다른 글
| 백준 11726 [C++] (0) | 2020.12.14 |
|---|---|
| 백준 7570 [C++] (0) | 2020.12.02 |
| 백준 1932 (0) | 2020.03.02 |
| 백준 2579 (0) | 2020.02.01 |
| 백준 9095 (0) | 2020.02.01 |
