강의자료에서
for x in range (1, k+1): # 가방 무게가 x일 때
# 물건을 담을 수 있을 때 (x보다 무게가 작거나 같을 때)
if x < weight :
dp[y][x] = dp[y-1][x]
# 물건을 담을 수 없을 때 ( 전에 넣어뒀던 무게로 유지)
else:
dp[y][x] = max(dp[y-1][x],dp[y-1][x-weight] + value )
이렇게 나와있는데, x < weight이면 물건을 못담을때 아닌가요??
Answer 2
0
안녕하세요, 인프런 AI 인턴입니다.
ukson 님께서 질문하신 부분은 강의에서 다루는 배낭 문제(Knapsack Problem)에서의 조건 표현 관련입니다. 말씀하신 부분에서 "x < weight"는 현재 가방의 남은 무게(x)보다 물건의 무게(weight)가 큰 경우를 의미합니다. 따라서 이 경우에는 물건을 담지 못합니다.
즉, 코드 상에서는 "x < weight" 조건문은 물건을 담을 수 없는 상황에 해당하며, 이때는 이전 상태를 유지해야 하므로 dp[y][x] = dp[y-1][x]로 설정됩니다.
반대로, else문 이하에서는, x >= weight인 경우, 즉 물건을 추가로 담을 수 있는 경우를 나타냅니다. 이 경우에는 물건을 담지 않을 때의 가치와, 물건을 담았을 때의 가치 중 더 큰 값을 선택하여 dp[y][x] = max(dp[y-1][x], dp[y-1][x-weight] + value)로 설정합니다.
배낭 문제에서 이와 같은 조건 설정은 매우 중요하며, 해당 조건에 따라 DP 상태 배열이 정확하게 갱신됩니다. 아래의 유사한 질문 링크에서 보다 상세한 설명을 보실 수 있습니다:
저는 질문자님의 이해를 돕기 위해 기존 관련 질문과 답변을 참고하여 설명드리고 있으며, 현재 베타 기능으로 제공되는 점 양해 부탁드립니다. 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다. 🙏
dp[x]가 최대값이라고 확신할수 있는 이유
0
44
1
1090번 문제 질문
0
148
1
유니온파인드
0
111
1
투포인터 25:15 질문
1
127
1
#1090번 문제 반례가 궁금합니다.
0
145
1
예제코드 자바입니다
1
186
1
정수론 파트 #2247 문제에 대한 질문입니다!
0
101
0
코드 오류
0
185
1
2강 정수론 문제3 #1407 질문
0
126
0
이차원 배열 (int형)dp로 0 혹은 -1로 체크하는 방법 말고 boolean형 배열로 체크해서 바로 리턴해줄 수 없나요?
0
154
0
1717번 최적화
0
112
0
백준 22988 문제 질문
1
192
2
[Python] 백준 1090번 문제
1
223
3
2503 문제 제한 조건 질문!
1
248
2
백준 22988 번 문제
1
191
1
추가 강의 순서
1
179
2
(*문제 풀이)1090 테스트케이스 1번 C++
1
219
2
7강 RGB 색칠하기 질문 있습니다.
1
160
2
정수론 약수 빠르게 구하기 질문
1
255
1
1090 문제의 2, 3번째 아이디어는 결국 같은거 아닌가요?
1
372
2
1090 문제 관련하여 맨해튼 거리 최솟값에 대해 질문 있습니다.
1
222
2
누적합 문제 3번 질문
1
214
2
기억 ( 누적합 ) 강의 11660 문제
1
162
2
14719
1
204
2