알고리즘 문제 해결전략 책 내용 질문이 있습니다! issuemine 우선 책 너무 잘 보고 도움이 되서 저자님에게 감사하다는 말씀 먼저드립니다 ^^ 그런데 책 코드 중에 동적계획법 메모리제이션 방법중에 int pack(int capacity, int item){ if(item==n) return 0; int ret=cache[capacity][item]; if(ret!=-1) return ret; ret=pack(capacity,item+1); if(capacity>=weight[item]){ ret=max(ret,pack(capacity-weight[item],item+1)+need[item]); } return ret; } 이런 코드가 많이 보이더라고요. int ret=cache[capacity][item] 은 cache에 저장되어있는 정보가 이미 존재하면 같은 계산을 하지 않기 위해서 저렇게 하는건데 정작 중요한 cache배열에 값을 배정하는 배정문이 안 보이네요 일부로 뺴먹으신건지 실수로 빼먹으신건지 저 코드가 맞는건지 궁금하네요 제 생각엔 return ret를 return cache[capacity][item]=ret 로해야되는 것이 맞는거 같은데 맞나요? 9년 전
2개의 댓글이 있습니다. kcm1700 issuemine님이 써주신 방법으로 하셔도 됩니다. 그런데 아마 책에 나오는 코드에는 int &ret = cache[...]; 로 되어있을 겁니다. C++에서 &를 붙여서 저렇게 이름을 만들면 reference로 동작합니다. 즉 ret 값을 바꾸면 cache[...]의 내용도 같이 바뀌게 됩니다. 9년 전 link JongMan 위대하신 kcm님의 말씀이 옳습니다. 8.1절의 "메모이제이션 구현 패턴" 부분을 참조해 주세요. 9년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
issuemine
우선 책 너무 잘 보고 도움이 되서 저자님에게 감사하다는
말씀 먼저드립니다 ^^
그런데 책 코드 중에 동적계획법 메모리제이션 방법중에
int pack(int capacity, int item){
if(item==n) return 0;
int ret=cache[capacity][item];
if(ret!=-1) return ret;
ret=pack(capacity,item+1);
if(capacity>=weight[item]){
ret=max(ret,pack(capacity-weight[item],item+1)+need[item]);
}
return ret;
}
이런 코드가 많이 보이더라고요.
int ret=cache[capacity][item] 은 cache에 저장되어있는 정보가
이미 존재하면 같은 계산을 하지 않기 위해서 저렇게 하는건데
정작 중요한 cache배열에 값을 배정하는 배정문이 안 보이네요
일부로 뺴먹으신건지 실수로 빼먹으신건지 저 코드가 맞는건지
궁금하네요 제 생각엔
return ret를
return cache[capacity][item]=ret
로해야되는 것이 맞는거 같은데 맞나요?
9년 전