냅색, knapsack

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

10265번: MT

이 문제의 기본 아이디어

 

 

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

 

 

 

냅색을 실제로 적용하려면 너무 어려운 것 같다 ㅜㅜ