6개의 댓글이 있습니다.
-
-
박선준 -
#include<iostream> #include<cstring> #include<algorithm> #define SIZE 100 using namespace std; int N, W, v, w; int dp[SIZE + 1][1001]; int max_index; int max_pick[SIZE]; int vol[SIZE + 1]; int hope[SIZE + 1]; char item[SIZE + 1][21]; int main() { int Case; cin >> Case; while (Case--) { memset(dp, 0, sizeof(dp)); cin >> N >> W; for (int i = 1; i <= N; i++) { cin >> item[i] >> vol[i] >> hope[i]; for (int j = 0; j <= W; j++) { if (j >= vol[i]) { if (dp[i - 1][j]<dp[i - 1][j - vol[i]] + hope[i]) { dp[i][j] = dp[i - 1][j - vol[i]] + hope[i]; } else { dp[i][j] = dp[i - 1][j]; } } else dp[i][j] = dp[i - 1][j]; } } max_index = 0; int temp = W; while (W!=0&&dp[N][W] == dp[N][W - 1]) W--; for (int i = N; i>0; i--) { if (vol[i] <= W) { if (dp[i][W] == dp[i - 1][W - vol[i]] + hope[i]) { max_pick[max_index++] = i; W -= vol[i]; } if (W == 0) break; } } cout << dp[N][temp] << " " << max_index << endl; for (int i = max_index - 1; i >= 0; i--) cout << item[max_pick[i]] << endl; // system("PAUSE"); } return 0; }
< / spoiler>
이런식으로 바꿔서 정답 나왔습니다 감사합니다 ㅋㅋㅋ 굳
음수 배열을 찍는데 런타임이 안뜨고 엉뚱한 값 뽑아서 디버그하기가 어려웠던 거네요 모든 조건에 대해서 배열 범위를 초과하지는 않는지 항상 확이 해야겠씀다!
8년 전 link정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
-
박선준
PACKING
책에 있는 방식으로 구현해서 패스를 받고 이후에 냅색문제를 공부하게 되면서 다시 이 문제를 풀어 보게 되었습니다.
dp[i][j]=max(dp[i-1][j],dp[i-1][j-wi]+vi) 1<=i<=N wi=<j<=W
점화식을 통해서 dp[101][1001]맵을 만들어서
dp[N][W]에 최대 절박도를 구하였습니다.
이어서 dp[N][W]에서 역으로
dp[i][j]==dp[i-1][j-wi]+vi인 지점을 찾아 저장 하는 방식으로
무엇을 뽑았는지 찾았습니다.
해당 방법이 책에 있는 방법과 어떤점이 다른건지
왜 패스가 안 나오는지 궁금함다!
8년 전