기술나눔

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

하나,2차원 배열

1、상태 전이 방정식：

• 항목을 넣지 마십시오i : dp[i - 1][j]에서 추론됩니다. 즉, 배낭 용량은 j이고 아이템 i의 최대값은 여기에 배치되지 않습니다. 이때 dp[i][j]는 dp[i -입니다. 1][j]. (실제로 아이템 i의 무게가 배낭 j의 무게보다 클 경우, 아이템 i를 배낭에 넣을 수 없으므로 배낭에 담긴 가치는 여전히 이전과 동일합니다.)
• 항목 i를 넣어: dp[i - 1][j - 무게[i]]에서 추론, dp[i - 1][j - 무게[i]]는 i가 j - 무게[인 경우 배낭의 최대 용량입니다. i] 값이면 dp[i - 1][j - Weight[i]] + value[i] (항목 i의 값)는 항목 i를 배낭에 넣었을 때 얻은 최대 값입니다.

따라서 재귀 공식은 다음과 같습니다. dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - Weight[i]] + value[i]);

2. 초기화

(1) dp[i][j]의 정의로부터 시작하여 배낭 용량 j가 0, 즉 dp[i][0]이면 어떤 항목을 선택하든 배낭의 총 가치는 다음과 같아야 합니다. 0.

(2) 상태 전이 방정식 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 가중치[i]] + value[i]); i는 i-1에서 파생되므로 i가 0일 때 초기화되어야 함을 알 수 있습니다.

dp[0][j], 즉 i는 0이며, 항목 번호 0을 저장할 때 용량별 배낭이 저장할 수 있는 최대값입니다.

그렇다면 j < Weight[0]일 때 dp[0][j]는 0이 되어야 한다는 것은 명백합니다. 왜냐하면 배낭 용량이 0번 항목의 무게보다 작기 때문입니다.

j >= Weight[0]인 경우 dp[0][j]는 값[0]이어야 합니다. 배낭 용량이 항목 번호 0을 담기에 충분하기 때문입니다.

for (int j = 0 ; j < weight[0]; j++) {
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

(3) 기타 첨자 초기화:

dp[i][j] = 최대값(dp[i - 1][j], dp[i - 1][j - 가중치[i]] + 값[i])

dp[1][1] = max(dp[0][1], dp[0][1- Weight[i]] + value[i])는 왼쪽 및 위에 있어야 합니다.

따라서 초기화가 되어 있어야 하며, 편의상 임의의 값으로 설정할 수 있으며 기본적으로는 0으로 초기화됩니다.

2. 1차원(롤링 배열)

1. 1차원 dp 배열에서 dp[j]는 다음을 의미합니다. 용량이 j인 배낭은 최대값이 dp[j]인 항목을 운반할 수 있습니다.

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

2. 초기화

(1) dp[0]=0, 용량이 0인 배낭에 담긴 항목의 최대값이 0이기 때문입니다.

(2) 아이템의 가치가 0보다 크다고 가정하고,초기값으로 덮어쓰이지 않도록, 그래서 DP어레이 초기화이면 처음에는 모두 0이다.

3. 순회 순서

역순으로 횡단

설명 1: 목록 끝에 있는 값은 이전 레벨을 탐색하여 얻은 이전 값과 비교하여 결정되어야 합니다.

설명 2: 각 백팩에는 01 백팩이 하나만 있습니다. 이 백의 배치 여부는 이전 백의 상태와 관련이 있습니다. 왼쪽의 배열은 이전 백의 상태를 설명하는 수량이며, 그 숫자는 오른쪽은 현재 가방의 보류 상태입니다. 코드에서 왼쪽의 숫자는 오른쪽의 배열을 결정하는 데 필요하므로 오른쪽의 숫자가 계산되기 전에는 왼쪽의 숫자가 소멸될 수 없습니다.

설명 3: 2차원의 경우, 내가 가지고 있는 각각의 새로운 dp 번호의 결과는 위쪽과 왼쪽에서 나옵니다. 실제로 1차원에서는 이와 같아야 하지만, 1차원에서는 여전히 왼쪽에서 오른쪽이라면 다음과 같습니다. 내 실제 왼쪽 수치가 업데이트되었습니다 ( 왼쪽은 더 이상 "원래" 왼쪽이 아닙니다!이로 인해 이중 계산이 발생합니다. ), 상단이 여전히 원래 상단인 경우에도 얻은 숫자가 올바르지 않습니다.그리고 배낭 레이어(내부 레이어)에서 오른쪽에서 왼쪽으로 탐색하면 왼쪽에 있는 요소는 항상이전 작업으로 인해 새로운 값으로 덮어쓰여지지 않습니다., 그래야 올바른 값을 얻을 수 있습니다.

3. 신청

1. 양의 정수만 포함하는 비어 있지 않은 배열이 제공됩니다. 이 배열을 두 개의 하위 집합으로 분할하여 두 하위 집합의 요소 합계가 동일하도록 하는 것이 가능합니까?

참고: 각 배열의 요소는 100을 초과할 수 없으며 배열의 크기는 200을 초과할 수 없습니다.

예시 1:

• 입력: [1, 5, 11, 5]
• 출력: 사실
• 설명: 배열은 [1, 5, 5] 및 [11]로 나눌 수 있습니다.

분석하다:

아이템은 나,

무게는 nums[i]이고 값도 nums[i]이며 배낭 부피는 sum/2입니다.

01 백팩과 유사함

상태 전이 방정식:

dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

// 开始 01背包
for(int i = 0; i < nums.size(); i++) {
    for(int j = target; j >= nums[i]; j--) {
        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    }
}
// 集合中的元素正好可以凑成总和target
if (dp[target] == target) return true;

2. 돌무더기가 있고, 각 돌의 무게는 양의 정수입니다.

매 라운드마다 두 개의 바위를 골라 함께 부수세요. 돌의 무게가 각각 x와 y이고 x <= y라고 가정합니다. 그러면 분쇄의 가능한 결과는 다음과 같습니다.

x == y이면 두 암석 모두 완전히 부서집니다.

x != y이면 x 무게의 돌은 완전히 부서지고 y 무게의 돌은 새로운 무게 yx를 갖게 됩니다.

결국에는 돌 하나만 남게 될 것입니다. 이 돌의 가능한 가장 작은 무게를 반환합니다. 남은 돌이 없으면 0을 반환합니다.

예:

• 입력: [2,7,4,1,8,1]
• 출력: 1

분석하다:

돌을 같은 무게의 두 더미로 나누어 충돌 후 가장 작은 돌이 남도록 하십시오.

그런 다음 두 개의 돌 더미로 나눕니다. 한 돌 더미의 총 무게는 dp[target]이고, 다른 더미의 총 무게는 sum - dp[target]입니다.

목표를 계산할 때, 반내림되기 때문에 target = sum / 2이므로 sum - dp[target]은 dp[target]보다 크거나 같아야 합니다.

그러면 충돌 후 남은 돌의 최소 무게는 (sum - dp[target]) - dp[target]입니다.

for (int i = 0; i < stones.length; i++) {
//采用倒序
    for (int j = target; j >= stones[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
    }
}
//结果
sum - 2 * dp[target];

인용 출처:코드 랜덤 노트