2022. 12. 29. 11:53ㆍboj
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
이문제의 경우
01 냅색 문제로 대표적인 내용이라고 한다.
여기서 처음 나는 선택을 할지 안할지를 1차원 배열을 기준으로 두고
문제를 해결하려고 하였다.
void solve(vector<vector<int>>& v, int idx, int val, int sum, int w) {
if (sum > w) {
return ;
}
if (dp[sum] != 0) {
if (dp[sum] < val) {
dp[sum] = val;
} else {
return ;
}
}
for (int i = idx; i < v.size(); ++i) {
if (sum + v[i][0] <= w) {
solve(v, i + 1, val + v[i][1], sum + v[i][0], w);
if (dp[sum + v[i][0]] < val + v[i][1])
dp[sum + v[i][0]] = val + v[i][1];
}
}
}
처음 로직은 위와 같았는데 값을 선택할 수 있으면 선택해서 미리 저장된 값이 존재하는지 확인한 후
크다면 변경하고 아니면 그만두는 로직을 선택하였다. 허나 위와 같은 코드는 제출하니 37% 정도에서 막히는것을 확인 할 수 있었고
여러 사람들에게 2차원으로 해결하라는 이야기를 듣게 되었다.
따라서 비슷한 로직으로 이전의 값을 가지고 더해서 체크하는 로직을 처리할 수 있도록
void solve(vector<vector<int>>& v, int n, int w) {
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= w; ++j) {
if (j + v[i - 1][0] <= w) {
dp[i][j + v[i - 1][0]] = max(
dp[i - 1][j + v[i - 1][0]], dp[i - 1][j] + v[i - 1][1]
);
}
}
}
}
위와 같이 처리하는 함수를 만들었고 동작시켰다 . 이또한 문제가 발생하였는데 왜 문제가 발생하였는지는 찾을 수 없엇고
혹시나 하는 마음에 이전의 값을 미리 저장을 시켜두는 로직을 추가하게 되었다.
void solve(vector<vector<int>>& v, int n, int w) {
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= w; ++j) {
if (j + v[i - 1][0] <= w) {
dp[i][j + v[i - 1][0]] = max(
dp[i - 1][j + v[i - 1][0]], dp[i - 1][j] + v[i - 1][1]
);
}
}
for (int j = 1; j <= w; ++j) {
dp[i][j] = max(dp[i - 1][j], dp[i][j]);
}
}
}
이렇게 로직을 작성하니 통과하였는데 아직 3 코드의 차이를 정확하게 찾지 못하였다. 알고 계시는 분은
댓글남겨주신다면 너무 감사할 것 같다.
'boj' 카테고리의 다른 글
1181cpp 문제 해결. (0) | 2022.12.30 |
---|---|
boj 11000번. 강의실 배정. (0) | 2022.12.29 |
별찍기-10 2447 (3) | 2022.12.26 |
1920 수찾기. (0) | 2022.12.25 |
보물 (0) | 2022.12.25 |