[가방 + DP] 가방 문제 + 면접 실례

경 동 필기시험 때 멱 을 구 하 는 문제 가 있 었 는데 토론 구역 에 큰 사람 이 가방 알고리즘 으로 문 제 를 풀 고 돌아 와 가방 문 제 를 복습 하 는 것 을 보 았 다.
N 개의 아 이 템, 1 개의 무 게 는 weight [i] 이 고 가 치 는 price [i] 입 니 다. 쉬 운 Vol 의 가방 에 넣 어서 가방 을 얻 는 방법 이 가장 가치 가 있 는 지 물 어 봅 니 다.
이런 문 제 는 0 - 1 가방, 완전 가방, 다 중 가방 문제 로 나 뉜 다.
0 - 1 가방: 아 이 템 당 1 개 만 있 음;
완전 가방: 모든 아 이 템 은 무한 개;
다 중 가방: 각 아 이 템 은 K 개;
0 - 1 가방:
DP： dp [i] [j] 는 j 의 가방 에 전 i 개의 아 이 템 을 넣 어 얻 은 최대 가 치 를 나타 낸다.
전달 관계: dp [i] [j] = max {dp [i - 1] [j], dp [i - 1] [j - weight [i]]] + price [i]};
설명: i 번 째 아 이 템 에 대해 서 는 두 가지 선택 이 있 습 니 다.
만약 에 설치 하지 않 으 면 dp [i] [j] 의 값 은 용량 이 j 일 때 전 i - 1 개 물품 만 얻 을 수 있 는 최대 가치 입 니 다.
만약 에 담 으 려 면 먼저 weight [i] 의 남 은 위 치 를 확보 해 야 합 니 다. 즉, j - weight [i] 입 니 다.
두 가 지 는 최대 치 를 취한 다. 즉, 전 i 항 아 이 템 을 가지 고 있 을 때 선택 할 수 있 는 가장 좋 은 값 이다.
교체 과정 에서 2 차원 배열 dp [i] [j] 의 수 치 는 그의 이전 줄 (dp [i - 1] [*]) 과 만 관련 되 기 때문에 2 차원 배열 은 1 차원 배열 로 최적화 하여 대체 할 수 있다 는 것 을 알 수 있다.

static int zeroOnePack(int [] weight, int [] price, int vol){
		
		int [] record = new int [vol + 1];
		
		for(int i = 0; i < weight.length; ++i){
			for(int k = vol; k >= weight[i]; --k){
				if(record[k] < record[k - weight[i]] + price[i])
					record[k] = record[k - weight[i]] + price[i];
			}
		}
		return record[vol];
	}

내부 순환 은 상한 선 에서 아래로 옮 겨 다 녀 야 합 니 다.
0 - 1 가방 이 라 아 이 템 당 1 회 만 담 을 수 있 습 니 다.
하한 선 부터 옮 겨 다 니 기 시작 하면 현재 아 이 템 의 성 비가 매우 높 으 면 가방 을 여러 번 반복 합 니 다.
이로써 완전 가방 이란 순환 하 는 방향 을 바 꾸 는 것 에 불과 하 다.
완전 가방

static int fullPack(int [] weight, int [] price, int vol){
		
		int [] record = new int [vol + 1];
		
		for(int i = 0; i < weight.length; ++i){
			for(int k = weight[i]; k <= vol; ++k){
				if(record[k] < record[k - weight[i]] + price[i])
					record[k] = record[k - weight[i]] + price[i];
			}
		}
		return record[vol];
	}

===================================================================
소 를 닦 는 손님 토론 구역 에서 본 면접 코드 문제 에 대해 큰 사람 이 설명 한 것 은 이중 가방 으로 설명 했다.
작성 자: Cavs 링크:https://www.nowcoder.com/discuss/48597?type = 0 & order = 0 & pos = 128 & page = 1 출처: 우 객 망 입력: 하나의 정수 배열 a, 최대 50 개의 요 소 를 포함 하고 모든 요소 의 합 은 1000 입 니 다.중복 요 소 를 포함 할 수 있 습 니 다.배열 에서 두 개의 서로 교차 하지 않 는 부분 집합 을 찾 아 두 개의 집중 요소 와 같 게 한다. 두 부분 집합 은 반드시 a 중의 모든 요 소 를 포함 하지 않 는 다. 즉, 요소 가 두 개의 집중 에 있 지 않 을 수 있다.이러한 조건 을 만족 시 키 기 위 한 최대 부분 집합 과 0 으로 돌아 가 는 것 은 존재 하지 않 습 니 다.예 를 들 어 a = [1, 2, 2, 3, 4, 6], 부분 집합 [1, 2, 3, 4] 과 [2, 2, 6] 조건 을 만족 시 키 기 위 한 두 부분 집합 은 10 으로 돌아간다.a = [1, 4, 5, 6], 부분 집합 [1, 5] 과 [6] 이 조건 을 만족 시 키 고 6 으로 돌아간다.
문제 풀이 코드:

import java.util.Arrays;

public class equalSubSet {
	static int maxSum = 1000;
	static boolean [][] dp = new boolean [maxSum][maxSum];

	public static void main(String[] args) {
		dp[0][0] = true;
		int [] nums = {1,2,2,2,3,4,6};
		for(int i = 0; i < nums.length; ++i){
			equalSubset(nums[i]);
		}
		for(int i = maxSum - 1; i >= 0; --i){
			if(dp[i][i]){
				System.out.println(i);
				break;
			}
		}
	}
	
	static void equalSubset(int num){
		
		for(int i = maxSum - 1; i >= 0; --i){
			for(int k = maxSum - 1; k >= 0; --k){
				if(k >= num && dp[i][k - num])
					dp[i][k] = true;
				if(i >= num && dp[i - num][k])
					dp[i][k] = true;
			}
		}
	}
}

이해: dp [i] [j
] true 일 때 첫 번 째 집합 에서 원 소 를 더 한 합 은 i 이 고 두 번 째 집합 에서 원 소 를 더 한 것 과 j 의 상황 이 성립 되 는 것 을 나타 낸다.
두 가지 상황 이 있 습 니 다. 첫 번 째 는 새로 온 num 이 첫 번 째 집합 에 추가 할 수 있 고 두 번 째 상황 은 새로 온 num 이 두 번 째 집합 에 추가 할 수 있 습 니 다.
첫 번 째 집합 에 dp [i] [j] 가 성립 되면 dp [i - num] [j] 가 성립 되 어야 하고 반대로 도 마찬가지 입 니 다.
마지막 으로 dp 의 대각선 에서 큰 것 에서 작은 것 으로 첫 번 째 트 루 값 을 찾 으 면 됩 니 다.
제목 에 크기 제한 이 있 기 때문에 1000 * 1000 배열 을 직접 신청 할 수 있 고 크기 는 받 아들 일 수 있 습 니 다.
시간 복잡 도 1000 * 1000 * 50.
앞으로 이와 유사 한 조합 성격 의 문 제 는 dfs 가지치기 외 에 도 가방 의 사고 에 대해 서도 생각 할 수 있다.