java - Javaの配列の例

Question

配列 int [] arr={1,2,4,5,7} があり、数字も 6 であると仮定すると、結果を 01100 にする必要があります。つまり、配列内で 2+4=6 になるため、結果は合計の数値が 0 の場合は 1 になり、それ以外の場合は、結果のビット数が配列の長さと同じ数になる必要があります

この操作を実行する Java メソッドが必要です

Answer 1

これは部分集合和問題と非常によく似ています。つまり、整数の集合が与えられた場合、空でない部分集合がゼロに等しいかどうかを判断します。あなたの場合、空でないサブセットが特定の整数に等しいかどうかを判断する必要があります。ビット配列への入力に関する後半部分は、純粋に装飾的なものです。

これを解決する簡単な方法は (つまり、あまり効率的ではありませんが)、O(2^N*N)配列内の可能なすべての整数のサブセット (べき乗セット) を循環させ、このサブセットの合計が与えられた数値に等しいかどうかを判断することです。

Answer 2

これを再帰的に行う方法を次に示します。JG が指摘したように、一般的な問題に対する効率的な解決策はありません。

private static int[] solve(int[] arr, int target, int res[], int length, int sum) {
    if (length == arr.length)
        return (sum == target)? res : null;
    res[length] = 0;
    int[] r = solve(arr, target, res, length + 1, sum);
    if (r != null)
        return r;
    res[length] = 1;
    r = solve(arr, target, res, length + 1, sum + arr[length]);
    if (r != null)
        return r;
    return null;
}

public static int[] solve(int[] arr, int target) {
    return solve(arr, target, new int[arr.length], 0, 0);
}