본문 바로가기
알고리즘/메모

냅색, knapsack

by sun__ 2019. 8. 19.

https://www.acmicpc.net/problem/10265

 

10265번: MT

문제 남규는 동기들과 엠티를 가기 위해 버스를 대절했다. 그런데 과사의 실수로 대절버스의 인원이 잘못되어 남규의 동기들을 모두 태울 수 없었다. 이 와중에 동기들은 화를 내며 다음과 같은 말들을 주고받았다. 재혁: 동우가 안 가면 나도 안 간다. 동우: 세종이가 안 가면 난 안 갈래. 버스에 태울 수 있는 인원수는 한정되어 있는데 모두들 다른 누군가가 가지 않으면 자신도 가지 않겠다 하니 남규는 신경이 뻗쳤다. 게다가 술을 너무 많이 샀기 때문에 최대한

www.acmicpc.net

이 문제의 기본 아이디어

 

 

작은 상자 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