백준 12865 평범한 배낭

문제 설명 :

문제에 제한된 무게내에서 최대의 가치를 담자

문제의 점화식
d[idx][kk] => 현재 idx까지 봤고 idx + 1을 보며 남은 무게가 kk일 경우 최대의 가치

문제 풀이 :

• 조건1. 가치를 더 할때 해당 남은 무게에 해당 무게를 빼게 될때 남은 무게가 0이상이 되어야한다
• 조건2. 무게를 더 했을경우나 더하지 않았을 경우 최댓값을 찾으면된다

dp테이블에 초깃값을 넣을때 아무것도 안해도 기본 가치는 0이기에
d[idx][kk] = 0을 넣는다

    //idx번째는 보고 idx + 1번째를 보려고하는 중이다. 
    if (kk - w[idx + 1] >= 0) {
        dp[idx][kk] = max(solve(idx + 1, kk - w[idx + 1]) + v[idx + 1], solve(idx + 1, kk));
    }
    else dp[idx][kk] = solve(idx + 1, kk);

 

전체코드 

https://github.com/kcj3054/algorithm/blob/master/12865.txt