베어_
TechBear
베어_
전체 방문자
오늘
어제
  • 분류 전체보기 (336)
    • Spring (33)
      • 개념 (13)
      • Security (5)
      • 실습 (1)
      • 토비 스프링 (11)
    • JPA (6)
    • 프로젝트 기록 (24)
    • DB (13)
    • JAVA (18)
    • 알고리즘 (50)
      • 유형정리 (8)
      • Baekjoon (21)
      • LeetCode (18)
    • 디자인패턴 (0)
    • 개발서적 (79)
      • Effective Java (78)
      • 객체지향의 사실과 오해 (1)
    • 독후감 (4)
    • 보안 (2)
    • 운영체제(OS) (53)
      • 공룡책 (53)
    • 컴퓨터 네트워크 (28)
      • 컴퓨터 네트워크 하향식 접근 (23)
    • 자료구조 (1)
    • DevOps (2)
    • 앱 개발 (20)
      • 안드로이드 스튜디오 (20)

블로그 메뉴

    공지사항

    인기 글

    태그

    • 알고리즘
    • BFS
    • 자바
    • leetcode
    • dfs
    • 코드업
    • java
    • 함수형인터페이스
    • 자바8
    • 스레드
    • Spring
    • 백준
    • 스프링시큐리티
    • 운영체제
    • 데이터베이스
    • jpa
    • 이펙티브자바
    • 스프링
    • C++
    • 토비스프링

    최근 댓글

    최근 글

    티스토리

    hELLO · Designed By 정상우.
    베어_

    TechBear

    [Baekjoon] 12865 평범한 배낭 문제
    알고리즘/Baekjoon

    [Baekjoon] 12865 평범한 배낭 문제

    2022. 3. 2. 21:02

    https://www.acmicpc.net/problem/12865

     

    배낭 문제는 냅색 알고리즘의 대표 문제라고 할 수 있다. 냅색 알고리즘은 다이나믹 프로그래밍에 속하는 알고리즘이다.

     

    문제의 입력 예제를 통해 냅색 알고리즘에 대해 알아보자. 

    1. 먼저 넣을 수 있는 무게 크기만큼 1차원 배열을 하나 준비하자. (dy라고 하겠다)

    2. 첫 번째 경우(4kg, 8원) 4kg의 가방에 8원의 가치를 가진 물건을 하나 넣을 수 있다. 5 - 7까지 모두 동일하다.

    3. 두 번째 경우(5kg, 6원) 5kg의 가방에 6원의 가치를 가진 물건을 넣을 수는 있지만 이전 값인 8이 더 크므로 4kg, 8원짜리 물건을 넣는다. 

     

     

    4. 세 번째 경우(3kg, 2원)

      -> 3kg의 가방에 2원짜리 물건을 넣을 수 있다. 

      -> 4kg -6kg 의 가방에 넣을 수는 있지만 이전의 값들이 더 크다.

      -> 7kg의 가방에는 3kg와 4kg 물건을 각각 한 개씩 넣어서 10원의 가치르 가진 가방을 만들 수 있다. 

      -> 여기서 7원의 값이 변경되는 코드는 다음과 같다. (a[j-w] + v > a[j])

     

    이 알고리즘을 적용해서 이 문제를 풀면 오답이 나온다. 이유는 다음과 같다.

    1kg, 10원의 가치를 가진 물건이 있다고 할 때 다음과 같이 a[j-w] + v > a[j]를 이용하면 1kg, 10원의 물건은 하나 밖에 없는데 이를 여러번 가방에 넣은 꼴이 되어 버린다. 

     

    따라서 이 문제를 해결하기 위해 7kg 가방부터 거꾸로 알고리즘을 적용시킨다.

    import java.util.Scanner;
    
    public class Main {
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
    
            int n = sc.nextInt(); // 물품의 수
            int k = sc.nextInt(); // 준서가 버티는 무게
            int[] bag = new int[k+1];
    
            for(int i = 0; i < n; i++) {
                int w = sc.nextInt();
                int v = sc.nextInt();
                for(int j = k; j >= w; j--) {
                    bag[j] = Math.max(bag[j], v + bag[j-w]);
                }
            }
    
            System.out.println(bag[k]);
        }
    }
      '알고리즘/Baekjoon' 카테고리의 다른 글
      • [백준] 7576 토마토 (JAVA)
      • [백준] 2606 바이러스(JAVA)
      • [백준] 10830 행렬 제곱 (JAVA)
      • [백준] 1629 곱셈 (JAVA)
      베어_
      베어_
      Today I learned | 문제를 해결하는 개발자

      티스토리툴바