말씀하신 가방 문제의 점화식 P[i][W] = Math.max(P[i-1][W], p[i] + P[i-1][W-w[i]])와, 질문자님이 짜신 코드의 결정적인 차이점을 아주 명확하게 짚어드리겠습니다.
결론부터 말씀드리면 차이는 딱 하나입니다.
"다음 단계를 위해 몇 개의 경우의 수(상태)를 저장해두었는가?" 입니다.
1. 질문자님의 코드: 하루에 "딱 1개의 결론"만 저장함
질문자님이 만드신 Food 객체 배열은 1차원 배열인 foods[i] 형태였습니다.
이 말은 **"i일차에 가장 싼 최적의 결과 딱 하나"**만 기억하겠다는 뜻입니다.
- foods[0] = 1일차 제일 싼 거 (예: 샐러드 10원)
- foods[1] = 2일차에 샐러드 빼고 고른 것 중 제일 싼 거
- foods[2] = ...
가방 문제로 치면 **"i번째 물건을 넣을지 말지 고민할 때, 무게 1~W까지 모든 경우를 계산하지 않고, 그냥 직전 단계에서 제일 가치가 높았던 결과 딱 1개만 기억해서 가져온 것"**과 같습니다. 이러면 배낭에 자리가 남았을 때 다른 물건을 조합할 기회를 영영 잃어버리게 됩니다.
'26년1학기 > 알고리즘' 카테고리의 다른 글
| 알고리즘) 문자열(1) (0) | 2026.05.18 |
|---|---|
| 알고리즘) 코드1 (0) | 2026.05.15 |
| 알고리즘) 과제4,3번(dp,dc) (0) | 2026.05.13 |
| 알고리즘) 배낭문제& np (0) | 2026.05.13 |
| 알고리즘) 프림 크루스칼 (1) | 2026.05.11 |