子集和問題

上一頁
下一頁

子集和問題

在**子集和問題**中，給定一個包含一些非負整數元素的集合。同時還提供一個和值，我們的任務是找到給定集合的所有可能的子集，其元素之和與給定的和值相同。

**集合：**在數學術語中，**集合**被定義為相似型別物件的集合。集合的實體或物件必須透過相同的規則相互關聯。

**子集：**假設有兩個集合，即集合P和集合Q。當且僅當集合P的所有元素也屬於集合Q時，集合P被稱為集合Q的子集，反之則不一定成立。

輸入輸出場景

假設給定的集合和和值如下：

 Set = {1, 9, 7, 5, 18, 12, 20, 15}
 sum value = 35

給定集合的所有可能的子集，其中每個子集的每個元素的和與給定的和值相同，如下所示：

 {1  9  7  18}  
 {1  9  5  20}  
 {5  18  12}

回溯法解決子集和問題

在解決子集和問題的樸素方法中，演算法生成所有可能的排列，然後逐個檢查有效解。每當一個解滿足約束條件時，將其標記為解的一部分。

在解決子集和問題時，回溯法用於選擇有效的子集。當一個專案無效時，我們將回溯以獲取先前的子集，並新增另一個元素以獲得解。

在最壞情況下，回溯法可能會生成所有組合，但是，通常情況下，它的效能優於樸素方法。

請按照以下步驟使用回溯法解決子集和問題：

  • 首先，取一個空子集。

  • 將下一個元素（索引為0）包含到空集中。

  • 如果子集等於和值，則將其標記為解的一部分。

  • 如果子集不是解並且小於和值，則向子集中新增下一個元素，直到找到有效的解。

  • 現在，轉到集合中的下一個元素並檢查另一個解，直到所有組合都已嘗試過。

示例

在本示例中，我們將說明如何在各種程式語言中解決子集和問題。

C C++ Java Python
#include <stdio.h>
#define SIZE 7
void displaySubset(int subSet[], int size) {
   for(int i = 0; i < size; i++) {
      printf("%d  ", subSet[i]);
   }
   printf("\n");
}
void subsetSum(int set[], int subSet[], int n, int subSize, int total, int nodeCount ,int sum) {
   if( total == sum) {
      //print the subset 
      displaySubset(subSet, subSize);  
      //for other subsets
      if (subSize != 0)
         subsetSum(set,subSet,n,subSize-2,total-set[nodeCount],nodeCount+1,sum);     
      return;
   }else {
      //find node along breadth 
      for( int i = nodeCount; i < n; i++ ) {     
         subSet[subSize] = set[i];
          //do for next node in depth
         subsetSum(set,subSet,n,subSize+1,total+set[i],i+1,sum);    
      }
   }
}
void findSubset(int set[], int size, int sum) {
   //create subset array to pass parameter of subsetSum
   int subSet[size];     
   subsetSum(set, subSet, size, 0, 0, 0, sum);
}
int main() {
   int weights[] = {1, 9, 7, 5, 18, 12, 20, 15};
   int size = SIZE;
   findSubset(weights, size, 35);
   return 0;
}

#include <iostream>
using namespace std;
void displaySubset(int subSet[], int size) {
   for(int i = 0; i < size; i++) {
      cout << subSet[i] << "  ";
   }
   cout << endl;
}
void subsetSum(int set[], int subSet[], int n, int subSize, int total, int nodeCount, int sum) {
   if( total == sum) {
      //print the subset 
      displaySubset(subSet, subSize);  
      //for other subsets
      subsetSum(set, subSet, n, subSize-1, total-set[nodeCount], nodeCount+1,sum);     
      return;
   }else {
      //find node along breadth 
      for( int i = nodeCount; i < n; i++ ) {     
         subSet[subSize] = set[i];
          //do for next node in depth
         subsetSum(set, subSet, n, subSize+1, total+set[i], i+1, sum);    
      }
   }
}
void findSubset(int set[], int size, int sum) {
   //create subset array to pass parameter of subsetSum
   int *subSet = new int[size];     
   subsetSum(set, subSet, size, 0, 0, 0, sum);
   delete[] subSet;
}
int main() {
   int weights[] = {1, 9, 7, 5, 18, 12, 20, 15};
   int size = 7;
   findSubset(weights, size, 35);
}

public class Main {
   static void displaySubset(int subSet[], int size) {
      for(int i = 0; i < size; i++) {
         System.out.print(subSet[i] + "  ");
      }
      System.out.println();
   }
   static void subsetSum(int set[], int subSet[], int n, int subSize, int total, int nodeCount ,int sum) {
      if( total == sum) {
         //print the subset 
         displaySubset(subSet, subSize);  
         //for other subsets
         if (subSize != 0)
            subsetSum(set,subSet,n,subSize-1,total-set[nodeCount],nodeCount+1,sum);     
         return;
      } else {
         //find node along breadth 
         for( int i = nodeCount; i < n; i++ ) {     
            subSet[subSize] = set[i];
            //do for next node in depth
            subsetSum(set,subSet,n,subSize+1,total+set[i],i+1,sum);    
         }
      }
   }
   static void findSubset(int set[], int size, int sum) {
      //create subset array to pass parameter of subsetSum
      int subSet[] = new int[size];     
      subsetSum(set, subSet, size, 0, 0, 0, sum);
   }
   public static void main(String[] args) {
      int weights[] = {1, 9, 7, 5, 18, 12, 20, 15};
      int size = 7;
      findSubset(weights, size, 35);
   }
}

def displaySubset(subSet, size):
    for i in range(size):
        print(subSet[i], end="  ")
    print()

def subsetSum(set, subSet, n, subSize, total, nodeCount, sum):
    if total == sum:
        #print the subset 
        displaySubset(subSet, subSize)
        #for other subsets
        if subSize != 0:
            subsetSum(set, subSet, n, subSize-1, total-set[nodeCount], nodeCount+1, sum)
        return
    else:
        #find node along breadth 
        for i in range(nodeCount, n):
            subSet[subSize] = set[i]
            #do for next node in depth
            subsetSum(set, subSet, n, subSize+1, total+set[i], i+1, sum)

def findSubset(set, size, sum):
    #create subset array to pass parameter of subsetSum
    subSet = [0]*size
    subsetSum(set, subSet, size, 0, 0, 0, sum)

if __name__ == "__main__":
    weights = [1, 9, 7, 5, 18, 12, 20, 15]
    size = 7
    findSubset(weights, size, 35)

輸出

1  9  7  18  
1  9  5  20  
5  18  12
列印頁面
上一頁
下一頁
廣告