궤도

문제 풀이 여러가지 풀이방법으로 풀 수 있는 냅색 문제이다. 이번엔 동적계획법으로 풀어야 한다. 특정 물건 i가 있다고 하자. 이 i에 대해 할 수 있는 것은 2가지이다. 배낭에 넣거나, 배낭에 넣지 않거나. 무조건 넣을 수 있는 것도 아니다. 버틸 수 있는 무게가 5인데 6짜리 물건은 넣을 수 없다. 그럼 어차피 못넣는 경우는 빼고, 넣을 수 있는 경우 이 물건을 넣어야 할까 말아야 할까? 1~N까지의 물건(i)과 1~K까지의 무게(j)가 있다고 하고 이걸 dp[i][j]라는 배열에 저장한다고 하자. 그니까 dp[2][4]라면 나에게 2개의 물건이 있고 4만큼의 무게를 들 수 있는 상황이라는 것이다. dp[i][j]에 대해 물건을 넣지 않을 경우 dp[i][j] = dp[i-1][j]이다. 물건을 넣지..