01 가방 문제 동적 기획 자바 실현 간단 하고 알 기 쉽다

**
01 가방 문제 동적 기획
**
1. 동적 기획
무엇이 동적 계획 입 니까?동적 계획 은 큰 문 제 를 끊임없이 아래로 나 누 어 작은 문제 로 나 누 는 것 이다. 분 리 된 작은 문제 가 해 를 구 할 수 있 을 때 까지 작은 문제 의 해 를 끊임없이 위로 통합 시 켜 큰 문제 의 해결 방안 을 얻 는 것 이다.2.01 가방 문제
한 여행 자 는 최대 m 킬로그램 을 담 을 수 있 는 가방 을 가지 고 있 습 니 다. 현재 n 개의 물건 이 있 습 니 다. 모든 무 게 는 W1, W2,..., Wn 입 니 다. 모든 물건 의 가 치 는 각각 C1, C2,..., Cn 입 니 다. 가방 에 물건 을 넣 어야 합 니 다. 어떻게 넣 어야 가방 에 있 는 물건 의 총 가치 가 가장 큽 니까?3. 간단 한 사고
1.01 가방 문제 와 가방 문제 의 차 이 는 01 가방, 아 이 템 의 선택 은 두 가지 만 가지 고 있 고, 다른 하 나 는 가지 고 있 지 않 으 며, 가방 문 제 는 아 이 템 의 일부분 만 찾 을 수 있다 는 점 이다.그래서 01 가방 문 제 는 욕심 산법 으로 해결 할 수 없습니다.2. dp [i] [j] 는 i 가지 물품 을 사용 하고 무 게 는 j 로 얻 은 가 치 를 나타 낸다.3. 제 i 종 아 이 템 에 대해 제 i 종 아 이 템 의 무게 가 j 보다 크 면 제 i 종 아 이 템 은 반드시 가 져 갈 수 없다 는 것 을 증명 한다. 이때 의 dp [i] [j] = dp [i - 1] [j] 4. 제 i 종 아 이 템 의 무게 가 j 보다 작 으 면 두 가지 상황 이 발생 한다. i 를 사용 하면 아 이 템 가치 dp [i] [j] = 앞의 i - 1 종 아 이 템 을 사용 하고 차지 하 는 무 게 는 j - i. getweight 로 발생 하 는 가치 + 제 i 종 아 이 템 의 가치.i 를 사용 하지 않 으 면, 가 치 는 dp [i - 1] [j] 입 니 다.수학 식 으로 바 꾸 면 dp [i] [j] = Math. max (dp [i - 1] [j - weight] + value, dp [i - 1] [j]);5. 예 를 들 어 i = 5, j = 10 일 때 dp [5] [10] 는 얻 은 가장 큰 가 치 를 대표 한다.여기까지 우 리 는 퀘 스 트 의 절반 을 완 수 했 습 니 다. 다음 에 어떤 물건 을 가방 에 넣 었 는 지 찾 아 보 겠 습 니 다. 앞의 표현 식 에서 우 리 는 dp [i] [j] = dp [i - 1] [j - weight] 일 때 i 의 물건 을 가방 에 넣 었 습 니 다. 그래서 우 리 는 결과 부터 되 돌아 가기 시 작 했 습 니 다. 이런 상황 이 발생 하면 가방 에 물건 을 넣 었 다 는 것 을 설명 하고 물품 수 를 1 로 줄 였 습 니 다.무 게 를 i 로 줄 이 고 계속 하면 가방 에 넣 을 물건 을 구 할 수 있 습 니 다.
예제:
1. 제목 설명:
다음 과 같은 5 가지 물건 이 있 는데 샤 오 밍 의 가방 은 최대 8 킬로그램 밖 에 안 되 는 물건 이다. 샤 오 밍 은 특히 욕심 이 많아 서 자신의 가방 을 어떻게 선택 하여 담 을 수 있 고 얻 을 수 있 는 가치 가 가장 큰 지 생각한다.
물품 1: 6 킬로그램 가치 48 원 물품 2: 1 킬로그램 가치 7 원 물품 3: 5 킬로그램 가치 40 원 물품 4: 2 킬로그램 가치 12 원 물품 5: 1 킬로그램 가치 8 원
2. 문제 풀이 방향:
사실 우 리 는 정상 적 인 사 고 를 할 때 보통 내 가 가능 한 한 8 킬로그램 을 채 우 고 가장 큰 가 치 를 구 해 야 한다 고 생각한다. 그러나 그러면 재 귀 를 사용 해 야 한다. 재 귀 는 풀 수 있 지만 알고리즘 이 어렵 을 뿐이다.그러나 동태 계획 이 무엇 인지 동태 계획 은 바로 거꾸로 하 는 것 이다. 나 는 8 킬로그램 의 물품 을 어떻게 포장 해 야 가치 가 가장 클 수 있 는 지 를 요구한다.나 는 먼저 0 킬로그램, 최대 가 치 를 고려 한 다음 에 1 킬로그램 의 최대 가 치 를 고려 하고 2 킬로그램 의 최대 가 치 를 고려 하여 3 킬로그램 의 최대 가 치 를 담 고 앞 에 모두 기록 할 수 있다.다른 temp [i] [j] 배열 로 기록 하 세 요.i 는 내 가 지금 나 오 는 물건 의 수량 을 나타 내 는데 i 가 마지막 수량 으로 순환 할 때 끝 나 잖 아.내 가 비록 다섯 개의 물건 을 가지 고 있 지만, 먼저 너 에 게 한 가지 만 줄 것 이 라 고 상상 해 봐. 네가 담 을 수 있 는 지 없 는 지 판단 해 봐. 그러면 네가 이 물건 을 담 을 수 있 는 지, 아니면 이 물건 을 담 을 수 있 는 지, 어떤 가치 가 높 은 지 기록 하면 돼.구체 적 으로 아래 의 표를 작성 해 보 세 요. 진정 으로 표를 작성 할 줄 아 는 것 은 많 지 않 습 니 다.

      0  1  2  3  4  5   6    7    8
      0  0  0  0  0  0   0    0    0
6 48  0  0  0  0  0  0   48  48   48
1 7   0  7  7  7  7  7   48  55   55
5 40  0  7  7  7  7  40  48  55   55
2 12  0  7  12 19 19 40  48  55   60
1 8   0  8  15 20 27 40  48  56   63 

이 시 계 는 어떻게 왔 습 니까?예 를 들 어 제 가 가로로 한 줄 씩 채 웠 을 때 처음에 한 가지 물건 만 떨 어 졌 기 때문에 무게 가 6 인 물건 이 떨 어 지기 시 작 했 고 6 이 되면 담 을 수 있 었 기 때문에 temp [1] [6] = 48, 그리고 7, 8 도 이 물건 만 채 웠 습 니 다.그래서 똑 같 아.
다음은 두 번 째 아 이 템 이 떨 어 졌 습 니 다. 1 이라는 아 이 템 이 떨 어 졌 습 니 다. 1 의 가 치 는 7, 즉 temp [2] [1] = 7 입 니 다.뒤 에는 temp [2] [5] 까지 모두 7 이다.포인트 가 왔 습 니 다. temp [2] [6] 때 가 되면 어 떡 하 죠?우리 의 것 은 당연히 내 가 첫 번 째 아 이 템 을 선택해 야 한 다 는 것 이다. 그 가 치 는 48 이지 만 첫 번 째 아 이 템 을 선택 하면 가방 이 꽉 차 서 두 번 째 무게 가 1 인 아 이 템 을 담 을 수 없다. 그래서 temp [2] [6] = 48.
우 리 는 이렇게 생각 할 수 있다. 관건 은 바로 컴퓨터 도 어떻게 이렇게 생각 할 수 있 느 냐 하 는 것 이다. 우 리 는 코드 를 사용 해 야 한다.사실 곰 곰 이 생각해 보 니 제 가 두 번 째 물건 을 떨 어 뜨 렸 습 니 다. 만약 에 담 을 수 없다 면 temp [2] [j] = temp [2] [j - 1] / / j 는 제 가방 이 지금 최대 j 만 담 을 수 있다 는 것 을 기억 합 니 다. 그러면 이 물건 을 담 을 수 없 으 니 당연히 담 을 수 없습니다.만약 내 가 현재 물품 의 무게 가 j 보다 작다 면, 나 는 포장 할 것 인지 안 할 것 인 지 를 선택 할 수 있 습 니까?엄 살 만 부 리 는 거 야, 안 부 리 는 거 야?만약 엄 살 을 부리 지 않 는 다 면 가 치 는 이때 의 가장 큰 가 치 는 변 하지 않 을 것 이다. 왜냐하면 엄 살 을 부리 지 않 기 때문이다. 즉, temp [2] [j] = temp [2 - 1] [j] 이다.내 가 담 으 면 관건 은 이것 이 냐, 아니면 아까 두 번 째 물건 의 가치 가 6 일 때 까지 냐 를 고려 해 보 자. 만약 에 내 가 무게 1 이라는 물건 을 담 으 면 temp [2] [6] = temp [2 - 1] [6 - 이 물건 의 무게] + 물건 의 가치 / /
사실 나 temp [2 - 1] [6 - 이 물건 의 무게] 는 내 가 아직 이 물건 을 담 기 전의 가 치 를 이 물건 을 담 을 공간 을 비 운 다음 에 이 물건 의 가 치 를 더 해서 비교 한 다 는 것 을 나타 낸다.문 제 는 이전의 모든 상 태 를 배열 로 기록 하 는 것 이다.키 코드 를 먼저 보고 코드 를 결합 해서 이해 하 세 요.

for(int i=1;i<6;i++) {
    for(int j=1;j<9;j++) {
        if(w[i]<=j) {
            temp[i][j] = Math.max(temp[i-1][j], temp[i-1][j-w[i]]+v[i]); //                  。
        }else {
            temp[i][j] = temp[i-1][j];// i      
        }
    }
}

3. 코드 예시

import java.util.Scanner;

public class knapsack {
	static int[] w = new int[6];//       
	static int[] v = new int[6];//       
	public static void solution(){
		
		
		int[][] temp = new int[6][9];//8        8     
		for(int j = 0;j < 9;j++){//      
			temp[0][j] = 0;
		}
		for(int i = 1;i < 6;i++){//     0 ，       0
			temp[i][0] = 0;
		}
		
		for(int i = 1;i < 6;i++){//         ，            ，     1-8        
			for(int j = 1;j < 9;j++){// i       5   ，      ， 5             
				if(w[i] <= j){//        ，     。         ，              
					temp[i][j] = Math.max(temp[i-1][j], temp[i-1][j-w[i]]+v[i]);
				}else{
					temp[i][j] = temp[i-1][j];// i      
				}
			}
		}
		for(int i = 0;i < 6;i++){
			for(int j = 0;j < 9;j++){
				System.out.print(temp[i][j] + " ");
			}
			System.out.println();
		}
	}
	public static void main(String[] args) {
		System.out.println("          :");
		Scanner scn = new Scanner(System.in);
		for (int i = 0; i < 6; i++) {
			w[i] = scn.nextInt();//    
			v[i] = scn.nextInt();//    
		}
		solution();
		
		
		
	}
}