정올1 [codeup][3740] 0/1 배낭 문제(Knapsack Problem) 문제 : http://codeup.kr/JudgeOnline/problem.php?id=3740 다이나믹 프로그래밍 DP의 대표 문제 중 하나인 물건을 넣느냐 빼느냐를 선택하는 0/1 배낭문제. 물건의 개수가 N이고 배낭에 담을 수 있는 최대 무게가 W이다. 물건은 종류별로 1개씩 있다. d[i][j] = 물건을 i번째 까지 배낭에 넣는다고 가정했을 때, 무게 j를 초과하지 않으면서 배낭에 넣을 수 있는 물건들의 가격의 총합의 최대값 d[i][j] = d[i - 1][j] (j = w[i]인 경우, i번째 물건을.. 2020. 2. 22. 이전 1 다음
