부분 집합 합 문제의 자세한 예
참고: "하위 집합 및 문제"에 대한 연구가 충분히 심층적이지 않기 때문에 이 문서에는 동적 프로그래밍 재귀 공식을 설명하는 데 불분명한 설명이나 오류가 있을 수 있습니다. 발견하면 알려주시기 바랍니다.
부분 집합 합 문제는 다음과 같이 설명할 수 있습니다. n 양의 정수 W=(w1, w2, …, wn) 및 양의 정수 M , ∑wi=M,i∈I[1]과 같은 a 하위 집합 I⊆{1, 2, 3, ..., n},을 찾아야 합니다. 부분 집합 합 문제에 대한 대중적인 설명을 제공하는 예를 들어보겠습니다. 집합 W=(1, 2, 3, 4, 5), 주어진 양의 정수 M=5, 존재합니까 W 의 하위 집합 I. 하위 집합 I에 있는 요소의 합은 M과 같습니다. 이 예에는 분명히 하위 집합 I=(2, 3).
문제 정의: 양의 정수 집합 S=(w1, w2, w3, …, wn), 주어진 양의 정수 W, s[i, j] i은 S의 하위 집합을 나타내고, j은 하위 집합 i의 합을 나타냅니다. S의 특정 집합 i의 요소 합 j=M이면 문제에 해결책이 있습니다.
예: S=(7, 34, 4, 12, 5, 3), W=6, S의 하위 집합이 있습니까? 해당 요소의 합은 같습니다. W으로.
이 문제에 대한 해결책도 많이 있습니다. 이 기사에서는 이를 해결하기 위해 동적 프로그래밍 아이디어를 사용하므로 재귀 공식을 도출해야 합니다. 우리는 계속해서 집합 S을 작은 집합으로 나눕니다. 이것이 동적 프로그래밍의 첫 번째 단계: 하위 문제 정의입니다. 집합 S의 가장 작은 집합은 물론 빈 집합이 존재하지 않으며 해당 요소의 합은 j=0과 같습니다. 빈 세트는 자격이 있습니다.
이 테이블의 열은 집합에 있는 요소의 합을 나타내며, 최대 W 요소에만 도달할 수 있습니다. 물론 W보다 크면 의미가 없습니다. 1이 j=6 열에 나타나면 문제에 대한 해결책을 얻을 수 있습니다. 행은 첫 번째 i(i 포함) 요소로 구성된 하위 집합을 나타냅니다(이 문장은 약간 의심스러울 수 있습니다. 모든 상황을 스캔하는 것이 가능하지 않을까요? 그런 다음 계속 읽으세요). i=0은 빈 집합을 의미합니다.
j=6일 때 빈 집합 상황은 true이라고 정의합니다. 그런 다음 j=0이면 이는 모든 하위 집합 합계에 해당됩니다(빈 집합이 해당 하위 집합임). 따라서 양식은 아래와 같이 계속 채워집니다.
이것은 실제로 동적 프로그래밍의 세 번째 단계인 초기 상태 정의입니다. 상태 계획의 두 번째 단계는 상태 전환 규칙, 즉 상태 간의 순환 관계를 정의하는 것입니다. s[i, j]의
i은 첫 번째 i하위 집합 (에는 i 포함)을 나타냅니다. 실제로 여기서는 이를 두 부분으로 나눕니다.
1)i번째 요소의 첫 번째 i 하위 집합, 즉 s[i - 1, j]을 제외합니다. ;
2)i번째 요소의 첫 번째 i 하위 집합을 포함합니다. 첫 번째
1) 상황의 경우 첫 번째 i - 1 집합 요소의 합은 j과 같고, 첫 번째 에 대한 하위 집합 요소가 있습니다. i 합계는 j과 같습니다.
이해하기 어려운 것은 2)상황입니다. 두 번째 경우에 대해 명확하게 알 수 있는 한 가지는 i in s[i, 수학에서 "특수 값 방법"을 사용하는 경우(예: (3, 34, 9) 집합) 요소의 합이 과 같은 하위 집합이 있습니까? 37, 이때 i=2(하위 집합은 (3, 34)), j = 37, 이때 "에는 첫 번째 이 포함됩니다. i isubset"의 경우, s[2, 37] => s[2, 37 - 34] = s[2, 3], 하위 집합 (3 , 34)물론 요소의 합이 3인 부분 집합도 있습니다. 그렇다면 j = 36, s[2, 36] => s[2, 36 - 34] = s[2, 2], 부분 집합 (3, 34) 요소의 합이 2인 부분 집합은 없습니다. j = 1, s[2, 1] => s[2, 1 - 34] = s[2, -32], j - wi < , 현재 s[2, 1] => s[2 - 1, 1] = s[1, 1], 하위 집합 (3)은 분명히 하위 집합 요소 중에 존재하지 않습니다. 합계는 1과 같습니다. 요약하면 재귀 수식은 다음과 같습니다. 이 알고리즘을 코드에 구현하기 전에 먼저 재귀 수식을 통해 위의 행렬을 채워야 합니다. ①i = 1, 이때 부분집합은 (7)
,
j = 1
∉(∅), 선택 상황 2) => [0 , 1] || s[1, -6] (i = 0은 빈 집합을 나타냄) 분명히 s[1, 1] = 0입니다. ②i = 1, 이때 부분집합은 (7), j = 2, j ∉(∅), 선택상황 2) => ] | s[1, -5] (i = 0은 빈 집합을 의미함) 당연히 s[1, 2] = 0입니다. , 이때 부분집합은 (7), j = 6, j ∉(∅), 선택 상황 2) => ; s[0, 6] || s[1, -1] (i = 0은 빈 집합을 나타냄) 분명히 s[1, 6] = 0입니다. 이때 하위 집합은 (7, 34, 4, 12, 5, 3), j = 1, j ∉ (7, 34, 4, 12, 5), 선택 상황 2) => 1] || s[6, -2] (i = 0은 빈 집합을 나타냄) 당연히 s[6, 1] = 0입니다. ②i = 6, (7, 34, 4, 12, 5, 3), j = 2, j ∉ (7, 34, 4, 12 , 5), 선택 상황 2) => s[5, 1] || s[6, -1] (i = 0은 빈 집합을 의미함) 당연히 s[6, 2] = 0입니다. ③i = 6, (7, 34, 4, 12, 5, 3), j = 3, j ∉ (7, 34, 4, 12 , 5), 선택 사례 2) => s[5, 1] || 당연히 s[6, 3] = 1입니다. ... ⑥i = 6, (7, 34, 4, 12, 5, 3), j = 6, j ∉ (7, 34, 4, 12 , 5), 선택 상황 2) => s[5, 6] || s[6, 3]. 당연히 s[6, 6] = 1입니다. Java
1 package com.algorithm.dynamicprogramming; 2 3 import java.util.Arrays; 4 5 /** 6 * 子集和问题 7 * Created by yulinfeng on 7/2/17. 8 */ 9 public class SubsetSumProblem {10 11 public static void main(String[] srgs) {12 int[] sets = {7, 34, 4, 12, 5, 3};13 int sum = 87;14 boolean isExistSubSet = subsetSumProblem(sets, sum);15 System.out.println("集合" + Arrays.toString(sets) + "是否存在子集的和等于" + sum + ":" + isExistSubSet);16 }17 18 private static boolean subsetSumProblem(int[] sets, int sum) {19 int row = sets.length + 1;20 int col = sum + 1;21 int[][] solutionMatrix = new int[row][col];22 solutionMatrix[0][0] = 1;23 24 /**25 * 0 1 2 3 4 5 626 * 0 |1|0|0|0|0|0|0|27 * 1 |x|x|x|x|x|x|x|28 * 2 |x|x|x|x|x|x|x|29 * 3 |x|x|x|x|x|x|x|30 * 3 |x|x|x|x|x|x|x|31 * 4 |x|x|x|x|x|x|x|32 * 5 |x|x|x|x|x|x|x|33 * 6 |x|x|x|x|x|x|x|34 */35 for (int i = 1; i < col; i++) {36 solutionMatrix[0][i] = 0;37 }38 /**39 * 初始状态40 * 0 1 2 3 4 5 641 * 0 |1|0|0|0|0|0|0|42 * 1 |1|0|x|x|x|x|x|43 * 2 |x|x|x|x|x|x|x|44 * 3 |x|x|x|x|x|x|x|45 * 3 |x|x|x|x|x|x|x|46 * 4 |x|x|x|x|x|x|x|47 * 5 |x|x|x|x|x|x|x|48 * 6 |1|0|0|x|x|x|x|49 * [i][0] = 1，按行填充50 */51 for (int i = 1; i < row; i++) {52 solutionMatrix[i][0] = 1;53 for (int j = 1; j < col; j++) {54 solutionMatrix[i][j] = solutionMatrix[i - 1][j];55 56 if (solutionMatrix[i][j] == 1) {57 solutionMatrix[i][j] = solutionMatrix[i][j];58 } else if ( j - sets[i - 1] >= 0 && solutionMatrix[i][j - sets[i - 1]] == 1) {59 solutionMatrix[i][j] = solutionMatrix[i][j - sets[i - 1]];60 } else {61 solutionMatrix[i][j] = 0;62 }63 64 if (j == col - 1 && solutionMatrix[i][j] == 1) {65 return true;66 }67 }68 }69 70 return false;71 }72 }
Python3
1 def subset_sum_problem(sets, sum): 2 row = len(sets) + 1 3 col = sum + 1 4 solutionMatrix = [[0 for col in range(col)] for row in range(row)] 5 solutionMatrix[0][0] = 1 6 for i in range(1, col): 7 solutionMatrix[0][i] = 0 8 9 for j in range(1, row):10 solutionMatrix[j][0] = 111 for k in range(1, col):12 solutionMatrix[j][k] = solutionMatrix[j - 1][k]13 if solutionMatrix[j][k] == 1:14 solutionMatrix[j][k] = solutionMatrix[j][k]15 elif (k - sets[j - 1] >= 0) and (solutionMatrix[j][k - sets[j - 1]] == 1):16 solutionMatrix[j][k] = solutionMatrix[j][k - sets[j - 1]]17 else:18 solutionMatrix[j][k] = 019 if k == col - 1 and solutionMatrix[j][k] == 1:20 return True21 22 return False23 24 sets = [7, 34, 4, 12, 5, 3]25 num = 626 is_exist = subset_sum_problem(sets, num)27 print(is_exist)
위 내용은 부분 집합 합 문제의 자세한 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
핫 AI 도구
Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱
AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.
Undress AI Tool
무료로 이미지를 벗다
Clothoff.io
AI 옷 제거제
AI Hentai Generator
AI Hentai를 무료로 생성하십시오.
인기 기사
뜨거운 도구
메모장++7.3.1
사용하기 쉬운 무료 코드 편집기
SublimeText3 중국어 버전
중국어 버전, 사용하기 매우 쉽습니다.
스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경
드림위버 CS6
시각적 웹 개발 도구
SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)
뜨거운 주제
7563
15
1385
52
84
11
61
19
28
99
C++ 코드에 나타나는 '오류: 'ClassName' 클래스 재정의' 문제 해결
Aug 25, 2023 pm 06:01 PM
C++ 코드에서 "error:redefinitionofclass'ClassName'" 문제를 해결하세요. C++ 프로그래밍에서는 다양한 컴파일 오류가 자주 발생합니다. 일반적인 오류 중 하나는 "error:redefinitionofclass 'ClassName'"('ClassName' 클래스의 재정의 오류)입니다. 이 오류는 일반적으로 동일한 클래스가 여러 번 정의될 때 발생합니다. 이 기사는
클러스터링 알고리즘의 클러스터링 효과 평가 문제
Oct 10, 2023 pm 01:12 PM
클러스터링 알고리즘에서 클러스터링 효과 평가 문제에는 특정 코드 예제가 필요합니다. 클러스터링은 데이터를 클러스터링하여 유사한 샘플을 하나의 범주로 그룹화하는 비지도 학습 방법입니다. 클러스터링 알고리즘에서는 클러스터링의 효과를 어떻게 평가하는가가 중요한 문제입니다. 이 기사에서는 일반적으로 사용되는 몇 가지 클러스터링 효과 평가 지표를 소개하고 해당 코드 예제를 제공합니다. 1. 클러스터링 효과 평가 지수 실루엣 계수 실루엣 계수는 표본의 근접성 및 다른 클러스터와의 분리 정도를 계산하여 클러스터링 효과를 평가합니다.
PHP 알고리즘 분석: 동적 프로그래밍 알고리즘을 사용하여 가장 긴 회문 부분 문자열 문제를 해결하는 방법은 무엇입니까?
Sep 19, 2023 pm 12:19 PM
PHP 알고리즘 분석: 동적 프로그래밍 알고리즘을 사용하여 가장 긴 회문 부분 문자열 문제를 해결하는 방법은 무엇입니까? 동적 프로그래밍(동적 프로그래밍)은 많은 복잡한 문제를 해결할 수 있는 일반적으로 사용되는 알고리즘 아이디어입니다. 그 중 하나는 문자열에서 가장 긴 회문 부분 문자열의 길이를 찾는 가장 긴 회문 부분 문자열 문제입니다. 이 기사에서는 PHP를 사용하여 이 문제를 해결하기 위한 동적 프로그래밍 알고리즘을 작성하는 방법을 소개하고 구체적인 코드 예제를 제공합니다. 먼저 가장 긴 회문 부분 문자열을 정의해 보겠습니다. 회문 문자열(palindrome string)은 앞으로 읽어도 뒤로 읽어도 같은 문자열을 말하며, 회문 문자열은
일반적인 iPhone 문제를 진단하는 방법을 가르쳐주세요.
Dec 03, 2023 am 08:15 AM
강력한 성능과 다재다능한 기능으로 잘 알려진 iPhone은 복잡한 전자 장치에서 흔히 발생하는 문제인 가끔씩 발생하는 문제나 기술적인 어려움으로부터 자유롭지 않습니다. iPhone 문제를 경험하면 실망스러울 수 있지만 일반적으로 알람은 필요하지 않습니다. 이 종합 가이드에서는 iPhone 사용과 관련하여 가장 일반적으로 직면하는 문제 중 일부를 쉽게 설명하는 것을 목표로 합니다. 당사의 단계별 접근 방식은 이러한 일반적인 문제를 해결하는 데 도움을 주고 장비를 최상의 작동 순서로 되돌릴 수 있는 실용적인 솔루션과 문제 해결 팁을 제공하도록 설계되었습니다. 결함이 있거나 더 복잡한 문제에 직면하더라도 이 문서는 문제를 효과적으로 해결하는 데 도움이 될 수 있습니다. 일반적인 문제 해결 팁 특정 문제 해결 단계를 진행하기 전에 다음은 몇 가지 유용한 정보입니다.
C#을 사용하여 동적 프로그래밍 알고리즘을 작성하는 방법
Sep 20, 2023 pm 04:03 PM
C#을 사용하여 동적 프로그래밍 알고리즘을 작성하는 방법 요약: 동적 프로그래밍은 최적화 문제를 해결하기 위한 일반적인 알고리즘이며 다양한 시나리오에 적합합니다. 이 기사에서는 C#을 사용하여 동적 프로그래밍 알고리즘을 작성하는 방법을 소개하고 특정 코드 예제를 제공합니다. 1. 동적 프로그래밍 알고리즘이란 무엇입니까? DP(동적 프로그래밍)는 중첩되는 하위 문제 및 최적의 하위 구조 속성 문제를 해결하는 데 사용되는 알고리즘 아이디어입니다. 동적 프로그래밍은 문제를 여러 하위 문제로 분해하여 해결하고 각 하위 문제에 대한 솔루션을 기록합니다.
jQuery가 양식 요소 값을 얻을 수 없는 문제를 해결하는 방법
Feb 19, 2024 pm 02:01 PM
jQuery.val()을 사용할 수 없는 문제를 해결하려면 구체적인 코드 예제가 필요합니다. 프론트 엔드 개발자에게는 jQuery를 사용하는 것이 일반적인 작업 중 하나입니다. 그중에서도 .val() 메서드를 사용하여 양식 요소의 값을 가져오거나 설정하는 것은 매우 일반적인 작업입니다. 그러나 특정한 경우에는 .val() 메서드를 사용하지 못하는 문제가 발생할 수 있습니다. 이 문서에서는 몇 가지 일반적인 상황과 해결 방법을 소개하고 구체적인 코드 예제를 제공합니다. 문제 설명 jQuery를 사용하여 프런트 엔드 페이지를 개발할 때 때때로 다음과 같은 문제가 발생할 수 있습니다.
C++에서 배낭 문제 알고리즘을 사용하는 방법
Sep 21, 2023 pm 02:18 PM
C++에서 배낭 문제 알고리즘을 사용하는 방법 배낭 문제는 컴퓨터 알고리즘의 고전적인 문제 중 하나입니다. 배낭 문제는 주어진 배낭 용량에서 배낭에 넣을 항목을 선택하여 항목의 총 가치를 최대화하는 방법을 포함합니다. 이 기사에서는 배낭 문제를 해결하기 위해 C++에서 동적 프로그래밍 알고리즘을 사용하는 방법을 자세히 소개하고 구체적인 코드 예제를 제공합니다. 먼저, 배낭 문제의 입력과 출력을 정의해야 합니다. 입력에는 아이템의 무게 배열 wt[], 아이템의 값 배열 val[], 배낭의 용량 W가 포함됩니다. 출력은 어떤 객체가 선택되었는지입니다.
약한 지도 학습의 라벨 획득 문제
Oct 08, 2023 am 09:18 AM
약한 지도 학습의 라벨 획득 문제에는 특정 코드 예제가 필요합니다. 소개: 약한 지도 학습은 훈련에 약한 라벨을 사용하는 기계 학습 방법입니다. 기존 지도 학습과 달리 약한 지도 학습은 각 샘플에 정확한 라벨이 필요한 것이 아니라 모델을 훈련하는 데 더 적은 수의 라벨만 사용하면 됩니다. 그러나 약한 지도 학습에서는 약한 레이블로부터 유용한 정보를 정확하게 얻는 방법이 핵심 문제입니다. 이 기사에서는 약한 지도 학습의 레이블 획득 문제를 소개하고 구체적인 코드 예제를 제공합니다. 약한 지도 학습의 라벨 획득 문제 소개:
