https://www.acmicpc.net/problem/10265
이 문제의 기본 아이디어
작은 상자 n개에 사탕이 최소 mn개 최대 mx개 들어있을 때, 용량이 K인 큰 바구니에 최대 몇개의 사탕을 넣을 수 있을까?
용량이 작을 땐 그리디하게도 접근할 수 있을 것 같지만 k가 1e6이상 큰 값이라면 힘들어 보인다.
knapsack(pos, cap)
: pos번쨰 상자부터 마지막 상자까지 사탕을 담을 때 고를 수 있는 사탕의 최대값을 반환한다.
//pos번째 상자부터 마지막 상자까지 골랐을 때 고를 수 있는 사탕의 최대값을 반환한다.
int knapsack(int pos, int cap){
if(cap>=K) return 0;
int &ret = dp[pos][cap]
if(ret!=-1) return ret;
ret = knapsack(pos+1, cap); //해당 pos에서 사탕을 줍지 않을 경우
for(int i=mn[pos]; i<=mx[pos]; i++){
if(i>cap) break;
ret = max(ret,knapsack(pos+1, cap-i)+i);
}
return ret;
}
냅색을 실제로 적용하려면 너무 어려운 것 같다 ㅜㅜ
'알고리즘 > 메모' 카테고리의 다른 글
KMP (0) | 2019.09.18 |
---|---|
lazy propagation - 세그먼트 트리 확장 (0) | 2019.09.18 |
기하 - 두 선분 사이의 거리 (0) | 2019.08.19 |
기하1 - 외적, 두 선분의 교차 (0) | 2019.08.19 |
2-SAT(Boolean Satisfiability) (0) | 2019.08.19 |