냅색

[Python]알고리즘/백준

[다이나믹 프로그래밍] 7579번 - 앱

[백준] 7579번 - 앱 (한줄평) 전에 풀었던 냅색 문제를 잘 이해했다면 어렵지 않게 해결핧 수 있었던 문제. 하지만 더 좋은 풀이를 생각해봐야할 문제로 다음에 다시 한번 풀어보면 좋을 것 같다. 유사 문제: 12865 https://hseungyeon.tistory.com/search/%EB%83%85%EC%83%89 공부 hseungyeon.tistory.com 앱의 개수가 N, 필요한 메모리가 M일 때, 둘째 줄의 N개의 정수는 현재 활성화 되어 있는 앱 A1, ..., AN이 사용 중인 메모리의 바이트 수인 m1, ..., mN을 의미하며, 셋째 줄의 정수는 각 앱을 비활성화 했을 경우의 비용 c1, ..., cN을 의미한다 (단, 1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000,000이며,..

[Python]알고리즘/백준

[다이나믹 프로그래밍] ★★ 12865번 - 평범한 배낭(22.05.15 복습완료)

[백준] 12865번 - 평범한 배낭 (한줄평) 냅색 문제인지 모르고 풀었던... 생각보다 더 어려웠던 문제로 복습이 꼭 필요하다!!! 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. N개의 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 구하는 문제다. 이 문제는 전형적인 냅색 문제다. 1. 분할가능 배낭 문제(Fractional Knapsack Problem) 담을 수 있는 물건이 나누어질 때(설탕 몇 g) - 물건의 가격을 무게로 나누어 무게 대비 가격이 비싼 순서로 물건을 정렬해서 넣으면 쉽게 해결이 가능! - 배낭이 감당할 ..

HSY_mumu
'냅색' 태그의 글 목록