PACKING 질문드릴께요~!! kws4679 PACKING을 풀던중에 궁금한게 있어서 질문드립니다!! 하다가 잘 안되서 결국 책에있는방식으로 풀어서 테스트를 통과하긴 했는데요 처음에는 이렇게 풀었습니다. PACKING 이전에 LIS 에서 설명했던대로 완전탐색을 하면서 choices[101] 배열에 넣었습니다. #include <iostream> #include <vector> #include <cstring> using namespace std; vector<string> names,results; int volumes[101], desire[101], choices[101]; int cache[101][1001]; int n,w, counts=0; int desireSum(int index, int v, int count){ if(index>=n) return 0; int& ret = cache[index][v]; if(ret != -1) return ret; ret = desireSum(index+1, v, count); if(v+volumes[index] <= w){ int cand = desireSum(index+1,v+volumes[index],count+1)+desire[index]; if(ret < cand){ choices[count] = index+1; ret = cand; } } return ret; } int main(){ int c; scanf("%d", &c); while(c--){ memset(volumes, 0, sizeof(volumes)); memset(desire, 0, sizeof(desire)); memset(cache, -1, sizeof(cache)); memset(choices, 0, sizeof(choices)); names = vector<string>(); results = vector<string>(); counts = 0; scanf("%d %d", &n, &w); string name; for(int i=0;i<n;++i) { cin >> name; scanf("%d %d", &volumes[i], &desire[i]); names.push_back(name); } int result = desireSum(0,0,0); for(int i=0;i<n;++i) if(choices[i]) counts++; printf("%d %d\n", result, counts); for(int i=0;i<n;++i) if(choices[i]) printf("%s\n", names[choices[i]-1].c_str()); } return 0; } 여기서 index 는 물건의 인덱스, v 는 부피, count 는 물건을 고른 개수이므로, count번째에 index물건을 저장하는(골랐다면) 것이라고 생각했는데 잘 안나오네요 ㅠㅠ 이런식으로 접근하면 안되는건가요? 11년 전
3개의 댓글이 있습니다. JongMan 소스 코드 앞뒤에 빈줄을 하나씩 넣어주셔야 구문 강조가 잘 됩니다. 수정했으니 참고하세요. 실제 답변은 아랫분이.. 11년 전 link VOCList 1 3 2 a 2 10 b 1 1 c 1 1 위 예제를 살펴보세요. 11년 전 link VOCList @JongMan 글쓰기시 아래에 나오는 신텍스 하일라이팅 안내문 변경하는게 좋지 않을까요. 거기 예제도 앞뒤로 빈 줄이 없어서... 11년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
kws4679
PACKING을 풀던중에 궁금한게 있어서 질문드립니다!!
하다가 잘 안되서 결국 책에있는방식으로 풀어서
테스트를 통과하긴 했는데요 처음에는 이렇게 풀었습니다.
PACKING 이전에 LIS 에서 설명했던대로
완전탐색을 하면서 choices[101] 배열에 넣었습니다.
여기서 index 는 물건의 인덱스, v 는 부피, count 는 물건을 고른
개수이므로, count번째에 index물건을 저장하는(골랐다면) 것이라고
생각했는데 잘 안나오네요 ㅠㅠ 이런식으로 접근하면 안되는건가요?
11년 전