가방 9 강의 01 가방 문제

가방 9 강의 01 가방 문제
질문 설명:
현재 n 개의 물품 이 있 는데 그 중에서 i 개의 물품 의 무 게 는 w [i] 이 고 가 치 는 p [i] 이 며 1 개의 용량 이 v 인 가방 이 있 습 니 다. 가방 의 용량 을 초과 하지 않 는 상황 에서 얻 은 상품 의 가 치 를 합 쳐 최대 로 해 야 합 니 다.
문제 분석:
        우선, 어떤 선택 전략 을 취하 더 라 도 이 n 개의 상품 은 두 가지 가 발생 하고 두 가지 상태 만 발생 하 며 취하 거나 취하 지 않 을 수 있 습 니 다.        먼저 물품 의 총량 n = 1, 즉 하나의 물품 만 있다 고 가정 하면 최대 가 치 를 얻 으 려 면 두 가지 상황 으로 나 뉜 다. 하 나 는 가방 용량 이 이 상품 의 무게 보다 작 지 않 으 면 취한 다.둘째, 가방 용량 이 이 상품 의 무게 보다 적 으 면 포기 합 니 다.        현재 n = 2 를 가정 하고 모든 전략 을 매 거 하 는 방법 을 사용 하면 모두 네 가지 전략 을 얻 을 수 있다. 1 을 취하 든 2 를 취하 든 1 을 취하 지 않 든 둘 다 취하 든 둘 다 취하 지 않 든.        그러나 n 의 수치 가 비교적 크 면 매 거 진 형식 으로 모든 결 과 를 열거 하기 어렵 기 때문에 이 때 는 하나씩 고려 할 수 있다.n 번 째 물품 부터 물품 의 두 가지 상 태 를 고려 하여 첫째, n 번 째 상품 을 취 할 때 문 제 는 n - 1 번 물품 에서 일정한 수량의 물품 을 선택 하여 용량 이 v - w [n] 인 가방 에 넣 고 가방 용량 을 초과 하지 않 는 전제 에서 가장 큰 가 치 를 해결 하 는 것 으로 간략화 되 었 다. 우리 가 요구 하 는 문 제 는 간략화 된 문제 의 해결 에 n 번 째 물품 의 가 치 를 더 하 는 것 이다.둘째, n 번 째 아 이 템 을 포기 할 때 문 제 는 n - 1 번 아 이 템 에서 일정한 수량 을 선택 하여 용량 이 v 인 가방 에 넣 는 것 으로 간략화 되 었 다. 가방 용량 을 초과 하지 않 는 상황 에서 가장 큰 가 치 를 가진다. 이때 간략화 한 문제 의 해 는 바로 우리 가 요구 하 는 최종 적 인 해결 이다.        n 번 째 를 고려 한 다음 에 같은 방식 으로 n - 1 번, n - 2 번 을 고려 합 니 다.        마지막 을 고려 할 때 까지 가방 이 두 번 째 물건 부터 n 번 째 물건 까지 일정한 상품 을 선택 한 상황 에서 가방 의 남 은 용량 이 첫 번 째 물건 (즉, 우리 가 마지막 으로 고려 한 물건) 을 놓 을 수 있다 면 우 리 는 찾 고 놓 지 못 하면 버 릴 것 이다.
알고리즘 설계
        f [i] [v] 를 사용 하여 이전 i 개 아 이 템 중 일 부 를 골 라 v 용량 의 가방 에 넣 는 것 이 가장 큰 가치 라 고 밝 혔 다.        자세히 분석 해 보면 f [i] [v] 는 f [i - 1] [v - w [i] + p [i] 와 f [i - 1] [v] 의 최대 치, 즉 f [i] = max (f [i - 1] [v - w [i]]] + p [i], f [i - 1] [v]) 와 같다.        이것 을 분석 하면 이것 은 매우 뚜렷 한 귀속 문제 라 는 것 을 얻 기 어렵 지 않다.        여기 서 주의해 야 할 점 이 있 습 니 다. 제목 에 가방 을 가득 채 우 는 것 이 아니 라 가방 용량 을 초과 하지 않 는 상황 에서 실제 사용 하 는 가방 용량 은 v 일 수도 있 고 v - 1, v - 2 심지어 0 일 수도 있 기 때문에 f [i] [v] 는 f [i] [v - 1] 과 같 을 수도 있 고 f [i] [v - 2] 와 같 을 수도 있 습 니 다. 심지어 f [i] [0] 은 실제 상황 에 따라 정 해 집 니 다.만약 에 이 n 개의 물품 의 무게 가 가방 의 총 용량 보다 크다 면 f [i] [v] 는 f [i] [0] 과 같다.
자바 구현

public class Page1 {
    private static int w[] = {2, 2, 2, 3, 5, 1, 3, 2, 7, 4, 2, 6};//  
    private static int p[] = {4, 4, 4, 6, 4, 1, 3, 8, 2, 1, 2, 4};//  
    private static int v = 7;
    public static void main(String[] args) {
        System.out.println(fun(w.length - 1, v));
    }
    public static int fun(int i, int v){
        if(i < 1){
            // i=0 ，                ，                   
            if(v >= w[i]){
                return p[i];
            }else{
                return 0;
            }
        }else{

            if(v < w[i]){
                //                    ，         
                return fun(i - 1, v);
            }else{
                //             
                return fun(i - 1, v) > fun(i - 1, v - w[i]) + p[i]?fun(i - 1, v):fun(i - 1, v - w[i]) + p[i];
            }
        }
    }
}

이상 은 제 가 01 가방 에 대한 간단 한 이해 입 니 다. 부족 한 점 이 있 으 면 지적 해 주 십시오.미 완성 계속...