-3
정수에 적합한 하위 집합 합계에 대해 다음 코드가 있습니다. 이 코드를 double 데이터 형식 입력으로 확장하는 방법은 무엇입니까? 예를 들어, 입력이 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]
이 질문은 파이썬과 관련이 있니? –
이 알고리즘에서는'double'을 합리적으로 사용할 수 없지만 정수가 될 때까지 입력의 크기를 조정할 수 있습니다. – harold
이 알고리즘의 복잡성은 무엇입니까? 매우 크거나 범위가 넓은 정수 (예 : 복식 크기를 늘릴 때와 같이)에서 작동합니까? – Thilo