[swexpert] 3282. 0/1 knapsack (dp, java)
Posted by 해랑쓰 블로그 (Haerang's blog)
각 물건의 무게를 쪼갤 수 없고 넣냐 빼냐로 결정하는 0/1 배낭 문제이다. dfs나 백트래킹으로는 2**n 승으로 오래걸려 시간 초과가 난다. dp로 풀어야만 풀리는 문제 dp[i][j]: 물건 i 번째에서 배낭 무게가 j일 때의 물건 가치 dp를 나누는 경우의 수 1. i 번째 물건이 무게 j보다 클 때: i 번째 물건을 무게가 j인 경우에 넣을 수 없어 이전 물건에서의 무게가 j인 가치를 넣어준다. dp[i][j]=dp[i-1][j]; 2. i 번째 물건이 무게 j보다 같거나 작을 때: dp[i][j]=Math.max(dp[i][j-w[i]]+cost[i],dp[i-1][j]); 이 문제는 물건 무게가 0인 경우가 없는데 만약 있는 문제라면 dp[i][j]=0; 으로 초기화해준다. import ja..