11

それはプログラミングの質問からです。

質問は次のとおりです。

数の配列は、除算する必要のある数kとともに与えられます。そして、それらの要素の合計がkで割り切れるように、その配列から要素を選択する必要があります。これらの要素の合計は、可能な限り大きくする必要があります。

入力：

最初の行nで、要素の数を示します。

次の行にn個の数字が表示されます。

次の行でkが与えられ、それによって除算する必要があります。

出力：

その配列から要素を選択することによって可能な最大の合計stsumはkで割り切れます。

サンプル入力：

5 
1 6 2 9 5
8

サンプル出力：

16

16は複数の数値の組み合わせで取得できますが、ここでは最大合計のみを考慮していることに注意してください。

私の提案する解決策：

配列をトラバースし、次のように、指定された入力配列の配列bの累積合計を維持します。

b=[1 7 9 18 23]

配列bの数値のmodをkで取得し、に格納します。

c=[1 7 1 2 7]

ここで、cで同じ値を持つ数値、つまりインデックス0とインデックス2。インデックス1とインデックス4。これですべてのソリューションが得られました。答えは次のようになります。

max(b[2]-b[0],b[4]-b[1])

そして、3つのインデックスがcで同じ値を持つ場合、つまり、

c=[1 2 3 1 1 2]

答えは

max(b[4]-b[0],b[5]-b[1])

基本的に、その番号の左端のオカレンスを右端のオカレンスから減算します。

私の解決策は、連続する要素がある場合にのみ機能します。要素の合計はkで割り切れます。正しい解決策の説明を期待する

4

5 に答える 5

14

あなたは連続した数字だけを考慮しているので、あなたの解決策は正しくないと思います。たとえば、入力が

4
1 6 2 9
8

答えは16（= 1 + 6 + 9）のままです。あなたの解決策がこの答えを与えることができるかどうかはわかりません。

この問題の効率的な解決策として、動的計画法を試してください。詳細は省略しますが、要点を指摘します。

番号がからまでの配列a[i]にあるとします。i1n

から（つまり）f(i,j)までの数値を選択することで得られる最大の合計を示します。また、合計を法として。a[1]a[i]a[1], a[2], ..., a[i]kj

考えてみてくださいf(i,j)。明らかに、2つの選択肢があります。（1）a[i]合計に含める。（2）を含めないでくださいa[i]。したがってf(i,j) = max{ f(i-1,x) + a[i], f(i-1,j) }、ここでx + a[i] == j (mod k)。境界はf(0,j) = 0すべてのためですj

このアルゴリズムを実装するための基本的なスケルトンは次のとおりです。

for (j = 0; j < k; j++) f[0][j] = 0;
for (i = 1; i <= n; i++)
  for (j = 0; j < k; j++) {
    x = (j + k - a[i]%k) % k;
    f[i][j] = max(f[i-1][x], f[i-1][j]);
  }

メモリを節約するために、次の[2][k]代わりにサイズの配列を使用することもでき[n][k]ます。

for (j = 0; j < k; j++) f[0][j] = 0;
for (i = 1; i <= n; i++)
  for (j = 0; j < k; j++) {
    x = (j + k - a[i]%k) % k;
    f[i%2][j] = max(f[(i-1)%2][x], f[(i-1)%2][j]);
  }

i&1（および(i-1)&1）を使用して、のモジュロを高速化することもできます2。

動的計画法に関するその他の参考資料：

于 2012-11-22T11:53:29.137 に答える
4

サブセット和の変形のように聞こえます：最大の和がで割り切れるサブセットが必要ですk。

しましょうdp[i] = largest sum obtainable that gives remainder i modulo k。ただし、同じ要素を2回使用しないようにするには、モジュロのために2つの配列を使用する必要があります。dp（ ）の現在の値を含む配列と（dp2）dp1の以前の値を含む配列です。dp我々は持っています：

a = original array
dp1[*] = dp2[*] = 0 
for i = 1 to n do
  for j = k - 1 down to 0 do
    dp1[j] = max(dp1[j], dp2[(j - a[i]) mod k] + a[i])

  copy dp1 to dp2: on the next iteration, the current array will must become the
  previous one (*)

（*）実行時間が非常に重要な場合は、必ずしもコピーを行う必要はないことに注意してください。配列dp[2, k]を使用して、その行を交互に使用できます。コンピューターからdp[0, _]からdp[1, _]奇数の反復で、またはその逆を偶数の反復で使用できます。

答えはまたはのいずれかになりdp1[0, 0]ますdp2[0, 0]。使用されるメモリはO(n + k)、時間計算量O(n * k)です。

注：これを実装する場合、負の値を回避するために、このようにモジュロを実行する必要がある場合があります((j - a[i]) mod k + k) mod k。または、を使用して、初期値が負の場合にifのみ追加することもできます。k

于 2012-11-22T11:59:11.627 に答える
4

注：番号がの特殊なケースでは3、答えは時間内に簡単に見つけることができますO(n log n)。

しましょうS = sum(array)。
さて、もしそうならS % 3 == 0、それSが答えです。
の場合S % 3 == 1、合計を除算3できるようにするには、のように最小の要素を削除するか、のように最小の要素iを削除i % 3 == 1します。 の場合、のような最小のもの、またはのような最小のものを削除できます。jkj % 3 == k % 3 == 2
S % 3 == 2ii % 3 == 2jkj % 3 == k % 3 == 1

于 2015-08-20T22:37:02.867 に答える
0 
import java.util.*;

public class MaxSumDivisible 
{

    static int max,divisor;

public static void main(String...okok)
{
    Scanner sc=new Scanner(System.in);
    String str=sc.nextLine();
    String ss[]=str.split(" ");
    LinkedList<Integer> list= new LinkedList<Integer>();
    for(int i=0;i<ss.length;i++)
    {
        list.add(Integer.parseInt(ss[i]));
    }
    divisor=sc.nextInt();
    FindMaxSum(list,0);
    System.out.println(max);
}
public static void FindMaxSum(LinkedList<Integer> list, int currentsum)
{
    if(currentsum%divisor==0 && currentsum>max)
    {
        max=currentsum;
    }

    for(int num:list)
    {
        LinkedList<Integer> li2= new LinkedList<Integer>(list);
        li2.remove(new Integer(num));
        FindMaxSum(li2,currentsum+num);

    }
}
}

それはどんな数でも機能します（intの場合のみ）。

于 2015-07-27T14:08:07.307 に答える
0

次のコードは、特定の番号3用です。3で割り切れる配列の要素の合計。これをさらに一般化できます。主なアイデアは、各mod 3について、到達可能な最大合計を追跡することです。時間計算量：O（N）。スペースの複雑さ：O（K）ここで、Kは合計を除算できる整数です。ここでK=3です。

class Solution {
    public int maxSumDivThree(int[] nums) {
        int[] dp = new int[3];
        dp[1] = dp[2] = Integer.MIN_VALUE;
        for(int x : nums) {
            int[] dpNext = new int[3];
            dpNext[0] = Math.max(dp[x%3] + x, dp[0]);
            dpNext[1] = Math.max(dp[(x+1)%3] + x,dp[1]);
            dpNext[2] = Math.max(dp[(x+2)%3] + x,dp[2]);
            dp = dpNext;
        }
        return dp[0];
    }
}

LeetCode WeeklyContest163問題へのリンク。

于 2019-11-17T04:31:39.427 に答える