2017-09-04 89 views
-3

我有以下適用於整數的子集合的代碼。如何將此代碼擴展爲雙數據類型輸入?例如,當輸入是1.01,2.65,3.08,4.07,5.12(比如說)和輸出是15.62(比如說)時,如何擴展這個相同的代碼。這些輸入和輸出都是示例,即使它們改變代碼也應該工作。雙數據類型的子集總和?

// A Java program to count all subsets with given sum. 
import java.util.ArrayList; 
public class subset_sum 
{ 
// dp[i][j] is going to store true if sum j is 
// possible with array elements from 0 to i. 
static boolean[][] dp; 

static void display(ArrayList<Integer> v) 
{ 
    System.out.println(v); 
} 

// A recursive function to print all subsets with the 
// help of dp[][]. Vector p[] stores current subset. 
static void printSubsetsRec(int arr[], int i, int sum, 
          ArrayList<Integer> p) 
{ 
    // If we reached end and sum is non-zero. We print 
    // p[] only if arr[0] is equal to sun OR dp[0][sum] 
    // is true. 
    if (i == 0 && sum != 0 && dp[0][sum]) 
    { 
     p.add(arr[i]); 
     display(p); 
     p.clear(); 
     return; 
    } 

    // If sum becomes 0 
    if (i == 0 && sum == 0) 
    { 
     display(p); 
     p.clear(); 
     return; 
    } 

    // If given sum can be achieved after ignoring 
    // current element. 
    if (dp[i-1][sum]) 
    { 
     // Create a new vector to store path 
     ArrayList<Integer> b = new ArrayList<>(); 
     b.addAll(p); 
     printSubsetsRec(arr, i-1, sum, b); 
    } 

    // If given sum can be achieved after considering 
    // current element. 
    if (sum >= arr[i] && dp[i-1][sum-arr[i]]) 
    { 
     p.add(arr[i]); 
     printSubsetsRec(arr, i-1, sum-arr[i], p); 
    } 
} 

// Prints all subsets of arr[0..n-1] with sum 0. 
static void printAllSubsets(int arr[], int n, int sum) 
{ 
    if (n == 0 || sum < 0) 
     return; 

    // Sum 0 can always be achieved with 0 elements 
    dp = new boolean[n][sum + 1]; 
    for (int i=0; i<n; ++i) 
    { 
     dp[i][0] = true; 
    } 

    // Sum arr[0] can be achieved with single element 
    if (arr[0] <= sum) 
     dp[0][arr[0]] = true; 

    // Fill rest of the entries in dp[][] 
    for (int i = 1; i < n; ++i) 
     for (int j = 0; j < sum + 1; ++j) 
      dp[i][j] = (arr[i] <= j) ? (dp[i-1][j] || 
        dp[i-1][j-arr[i]]) 
        : dp[i - 1][j]; 
    if (dp[n-1][sum] == false) 
    { 
     System.out.println("There are no subsets with" + 
       " sum "+ sum); 
     return; 
    } 

    // Now recursively traverse dp[][] to find all 
    // paths from dp[n-1][sum] 
    ArrayList<Integer> p = new ArrayList<>(); 
    printSubsetsRec(arr, n-1, sum, p); 
} 

//Driver Program to test above functions 
public static void main(String args[]) 
{ 
    int arr[] = {1, 2, 3, 4, 5}; 
    int n = arr.length; 
    int sum = 10; 
    printAllSubsets(arr, n, sum); 
} 
} 

輸出:[4,3,2,1] [5,3,2] [5,4,1]

+2

有什麼問題與Python有關嗎? –

+5

你不能在這個算法中合理地使用'double',但是你可以縮放輸入直到它們是整數。 – harold

+0

這個算法的複雜性是什麼?它是否適用於非常大或寬範圍的整數(例如,當您縮放倍數時會得到)? – Thilo

回答

0

我通過簡單地通過計算轉換雙到整數發現這個問題的答案小數位數乘以100(說)作爲算法使用此外,這種變化不會影響最終值在這種情況下,我將最終值除以100以獲得結果並以雙數據類型顯示它