knapsack2 Knapsack알고리즘 Knapsack알고리즘 아래와 같이 n개의 물건과 각 물건i의 무게Wi와 가치Vi가 주어지고 배낭의 용량은 W일때, 배낭에 담을 수 있는 물건의 최대가치를 찾는 문제를 다뤄본다. 단, 배낭에 담은 물건의 무게 합은 배낭의용량W를 초과하지 말아야 하고, 각 물건은 1개씩만 있다. 배낭 문제를 DP로 접근해보자. 변수는 물건, 물건의무게, 물건의가치, 배낭의 용량 총 4가지 이다. 이 중 물건과 물건의 무게는 부분문제를 정의하는데 반드시 필요하다. 왜냐하면 배낭이 비어있는 상태에서 시작하여 물건을 하나씩 배낭에 담는것과 안담는것을 현재 배낭에 들어있는물건의 가치의 합에 근거하여 결정해야 하기 때문이다. 또한 물건을 배낭에 담으려고 할 경우 배낭용량의 초과여부를 검사해야 한다. W : 배낭의 용량 (vi, w.. 2022. 4. 5. [Java] SWEA5215_ 햄버거다이어트 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [문제] 평소 햄버거를 좋아하던 민기는 최근 부쩍 늘어난 살 때문에 걱정이 많다. 그렇다고 햄버거를 포기할 수 없었던 민기는 햄버거의 맛은 최대한 유지하면서 정해진 칼로리를 넘지 않는 햄버거를 주문하여 먹으려고 한다. 민기가 주로 이용하는 햄버거 가게에서는 고객이 원하는 조합으로 햄버거를 만들어서 준다. 하지만 재료는 미리 만들어서 준비해놓기 때문에 조합에 들어가는 재료를 잘라서 조합해주지는 않고,.. 2022. 3. 17. 이전 1 다음
