정당성
-
배낭 문제는 주어진 무게를 지탱할 수 있는 배낭에 담을 수 있는 아이템의 총량을 최적화하는 문제입니다. 배낭의 크기, 아이템의 개수, 각 아이템의 무게와 가치를 고려하여 배낭에 넣을 수 있는 아이템의 가치를 극대화하는 조합을 찾는 것이 문제입니다.
-
배낭 문제는 광범위합니다. 0-1 배낭 문제수업 분수 배낭 문제로 나누어
- 배낭 문제의 예로는 백준 문제 #12865가 있는데 일반적인 배낭 문제는 풀었습니다.
0-1 배낭 문제
-
배낭에 있는 아이템을 분할할 수 없을 때 각각의 아이템을 배낭에 넣을지 여부를 결정하는 문제.
-
동적 프로그래밍으로 문제를 해결할 수 있습니다.
![[알고리즘이론] 파이썬 자료구조](https://file.foodle.kr/wp-content/plugins/contextual-related-posts/default.png "[알고리즘이론] 파이썬 자료구조")
접근하다
데이터 구조
- 물건의 무게와 가치를 저장하는 구조
- 항목 수 * 가방 무게만큼 데이터를 저장할 수 있는 2차원 배열
개념
- 아이템을 최적으로 조합해야 하므로 각 배낭의 무게에서 가장 좋은 값을 저장하고 다음 아이템을 검색할 때 이전 아이템까지의 결과값을 이용하면 해결할 수 있다.
- 사례 1 : 남은 배낭의 무게보다 물건의 무게가 더 큰 경우
-> 오브젝트가 들어갈 수 없기 때문에 배낭의 현재 무게에서 이전 오브젝트의 값을 현재 오브젝트의 값과 공간이 있는 이전 오브젝트의 값의 합과 현재 오브젝트에 대한 값을 비교합니다. - Case 2 : 아이템의 무게가 남은 백팩의 무게보다 작은 경우
-
항목이 일치할 수 있으므로 이전 항목을 찾을 때 동일한 가중치에 현재 항목의 값을 추가합니다.
일반화
- 위 개념을 일반화하면 다음과 같다.
표기법
공식
- 위의 일반식으로 생성된 2차원 배열의 최대값을 계산합니다.
- 위 개념을 일반화하면 다음과 같다.
코드 구현(C++)
#include <iostream>
#include <stdlib.h>
using namespace std;
struct thing{
int weight;
int value;
};
int n, k;
thing* things;
int main(){
cin >> n >> k;
things = new thing(n);
int ** mat;
mat = (int **) malloc(sizeof(int *) * (n));
for(int i = 0; i < n; i++){
cin >> things(i).weight >> things(i).value;
mat(i) = new int(k+1);
}
int max_val = 0;
for(int i = 0; i <= k; i++){
if(things(0).weight > i) mat(0)(i) = 0;
else mat(0)(i) = things(0).value;
}
max_val = mat(0)(k);
for(int i = 1; i < n; i++){
for(int j = 0; j <= k; j++){
if(j < things(i).weight) mat(i)(j) = mat(i-1)(j);
else{
int val1 = things(i).value + mat(i-1)(j-things(i).weight);
int val2 = mat(i-1)(j);
mat(i)(j) = val1 > val2? val1 : val2;
if(mat(i)(j) > max_val) max_val = mat(i)(j);
}
}
}
cout << max_val << endl;
}분수 배낭 문제
- 아이템을 분해하여 배낭에 넣을 수 있을 때 배낭에 들어갈 수 있는 최대값을 찾는 문제.
- Greedy 알고리즘이 문제를 해결합니다.
접근하다
- 품목은 분해할 수 있으므로 각 품목의 가치 대 중량 비율을 계산하십시오.
- 단위 중량당 값이 오름차순으로 항목을 정렬합니다.
- 가방에 있는 물건들을 정리하고, 마지막으로 가방에 넣을 수 없는 물건은 최대한 많이 넣습니다.
코드 구현(C++)
#include <iostream>
#include <algorithm>
using namespace std;
struct thing{
int weight;
int value;
double value_ratio;
};
bool cmp(thing t1, thing t2){
return t1.value_ratio > t2.value_ratio;
}
int n, k;
thing* things;
int main(){
cin >> n >> k;
things = new thing(n);
for(int i = 0; i < n; i++){
cin >> things(i).weight >> things(i).value;
things(i).value_ratio = (double) things(i).value / things(i).weight;
}
sort(things, things + n, cmp);
double max_val = 0;
int idx = 0;
while(1){
if(things(idx).weight > k){
max_val += things(idx).value_ratio * k;
break;
}
else{
max_val += things(idx).value;
k -= things(idx).weight;
}
idx++;
if(k == 0 || idx == n) break;
}
cout << max_val << endl;
}출처 및 링크
문제
https://leetcode.com/problems/add-two-numbers/