動的計画法での部分和問題

#動的計画法での部分和問題数え上げについて
n個の整数から自由に選んでxになる組み合わせを求めるプログラムを実装しています。ただし、順番も考慮した組み合わせの数を実装したいため、(1,4,5)の組み合わせがxを満たすとき、1ではなく3の階乗として個数を加算したいです。今の時点で、組み合わせを1として加算することはできたのですが、階乗として加算する方法が分からず行き詰っています。どのように実装すれば実現することができるかを教えていただきたいです。

java
1import java.util.Scanner;
2
3public class Main {
4
5  static final int mod = 1000000007;
6
7  public static void main(String[] args) {
8    Scanner sc = new Scanner(System.in);
9
10    int n = sc.nextInt();
11    int x = sc.nextInt();
12    
13    int a[] = new int[n];
14    for (int i = 0; i < n; i++) {
15      a[i] = sc.nextInt();
16    }
17
18    long[] dp = new long[x + 1];
19
20    dp[0] = 1;
21
22    for (int i = 0; i < n; i++) {
23      for (int j = x; j >= a[i]; j--) {
24        dp[j] += dp[j - a[i]];
25        // dp[j] %= mod;
26      }
27    }
28    System.out.println(dp[x]);
29  }
30}

jimbe

2021/12/04 06:40

3の階乗の求め方が分からないということでしょうか?

kazuma-s

2021/12/05 14:10

「n 個の整数」には負の数が含まれることもあるのでしょうか？

行動規範の内容に同意します

回答2件

「n個の整数」には同じ数はないのでしょうか？
例えば x が 10 の場合、(3,3,4) (3,4,3) (4,3,3) だと 3 の階乗ではありませんよね。

同じ数が無くて組み合わせを求めるだけなら、次のようなコードが書けます。

java
1import java.util.Scanner;
2
3class ArraySum {
4	int[] a;
5	boolean[] b;
6
7	ArraySum(int[] a) { this.a = a; b = new boolean[a.length]; }
8
9	void proc(int i, int sum) {
10		if (sum == 0) {
11			String s = "(";	
12			for (i = 0; i < a.length; i++)
13				if (b[i]) { System.out.print(s + a[i]); s = ","; }
14			System.out.println(")");
15		}
16		else if (i < a.length) {
17			b[i] = true;  proc(i + 1, sum - a[i]);
18			b[i] = false; proc(i + 1, sum);
19		}
20	}
21}
22
23class Main {
24	public static void main(String[] args) {
25		Scanner sc = new Scanner(System.in);
26		int n = sc.nextInt(), x = sc.nextInt(), a[] = new int[n];
27		for (int i = 0; i < n; i++) a[i] = sc.nextInt();
28		new ArraySum(a).proc(0, x);
29	}
30}

実行結果

text
15 10
23 1 4 2 5
3(3,1,4,2)
4(3,2,5)
5(1,4,5)

先頭の 2行は入力です。

投稿2021/12/04 17:04

編集2021/12/04 17:27

kazuma-s

総合スコア8224

ベストアンサー

組み合わせを保存すれば後は計算できそうですので、配列リストに保存するようにしてみました。
("組み合わせの要素数"だけあれば済むと思いますが、見た目が分かり難いので。)
必要な「個数」は dpp[data.x].p から計算してください。

java
1package teratail_java.q372208;
2
3import java.util.*;
4
5public class Main {
6
7  //static final int mod = 1000000007;
8
9  private static class DpPattern {
10    private List<int[]> p = new ArrayList<int[]>();
11
12    void add(int v, DpPattern other) {
13      if(other == null) {
14        p.add(new int[]{v});
15      } else {
16        for(int[] a : other.p) {
17          int[] newArray = Arrays.copyOf(a, a.length+1);
18          newArray[a.length] = v;
19          p.add(newArray);
20        }
21      }
22    }
23    boolean isEmpty() { return p.isEmpty(); }
24    @Override
25    public String toString() {
26      StringJoiner sj1 = new StringJoiner(",","{","}");
27      for(int[] a : p) {
28        StringJoiner sj2 = new StringJoiner(",","(",")");
29        for(int v : a) sj2.add(""+v);
30        sj1.add(sj2.toString());
31      }
32      return sj1.toString();
33    }
34  }
35
36  static class Data {
37    final int n, x;
38    final int[] a;
39    Data(int x, int[] a) {
40      this.n = a.length;
41      this.x = x;
42      this.a = a;
43    }
44  }
45
46  public static void main(String[] args) {
47    Data data;
48
49    //data = input();
50    data = new Data(10, new int[]{3,1,4,2,5}); //テスト
51    //data = new Data(12, new int[]{7,5,3,1,8}); //テスト2
52    //data = new Data(5, new int[]{1,1,4,1}); //テスト3
53    //data = new Data(4, new int[]{2,2,1,1}); //テスト4
54
55    long[] dp = new long[data.x + 1];
56
57    DpPattern[] dpp = new DpPattern[data.x + 1];
58    for(int i=0; i<dpp.length; i++) dpp[i] = new DpPattern();
59
60    dp[0] = 1;
61    print(dp, dpp, "init");
62
63    for (int i = 0; i < data.n; i++) {
64      for (int j = data.x; j >= data.a[i]; j--) {
65        dp[j] += dp[j - data.a[i]];
66
67        dpp[j].add(data.a[i], j==data.a[i]?null:dpp[j-data.a[i]]);
68
69        print(dp, dpp, "i="+i+", j="+j);
70        // dp[j] %= mod;
71      }
72    }
73    System.out.println("結果:" + dp[data.x] + dpp[data.x]);
74  }
75
76  private static Data input() {
77    try(Scanner sc = new Scanner(System.in);) {
78
79      int n = sc.nextInt();
80      int x = sc.nextInt();
81
82      int a[] = new int[n];
83      for (int i = 0; i < n; i++) {
84        a[i] = sc.nextInt();
85      }
86      return new Data(x, a);
87    }
88  }
89
90  private static void print(long[] dp, DpPattern[] dpp, String header) {
91    System.out.print(header+": [");
92    for(int i=0; i<dp.length; i++) {
93      System.out.print((i==0?"":", ") + dp[i]);
94      if(!dpp[i].isEmpty()) System.out.print(dpp[i]);
95    }
96    System.out.println("]");
97  }
98}

実行結果

plain
1init: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
2i=0, j=10: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
3i=0, j=9: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
4i=0, j=8: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
5i=0, j=7: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
6i=0, j=6: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
7i=0, j=5: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
8i=0, j=4: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
9i=0, j=3: [1, 0, 0, 1{(3)}, 0, 0, 0, 0, 0, 0, 0]
10i=1, j=10: [1, 0, 0, 1{(3)}, 0, 0, 0, 0, 0, 0, 0]
11i=1, j=9: [1, 0, 0, 1{(3)}, 0, 0, 0, 0, 0, 0, 0]
12i=1, j=8: [1, 0, 0, 1{(3)}, 0, 0, 0, 0, 0, 0, 0]
13i=1, j=7: [1, 0, 0, 1{(3)}, 0, 0, 0, 0, 0, 0, 0]
14i=1, j=6: [1, 0, 0, 1{(3)}, 0, 0, 0, 0, 0, 0, 0]
15i=1, j=5: [1, 0, 0, 1{(3)}, 0, 0, 0, 0, 0, 0, 0]
16i=1, j=4: [1, 0, 0, 1{(3)}, 1{(3,1)}, 0, 0, 0, 0, 0, 0]
17i=1, j=3: [1, 0, 0, 1{(3)}, 1{(3,1)}, 0, 0, 0, 0, 0, 0]
18i=1, j=2: [1, 0, 0, 1{(3)}, 1{(3,1)}, 0, 0, 0, 0, 0, 0]
19i=1, j=1: [1, 1{(1)}, 0, 1{(3)}, 1{(3,1)}, 0, 0, 0, 0, 0, 0]
20i=2, j=10: [1, 1{(1)}, 0, 1{(3)}, 1{(3,1)}, 0, 0, 0, 0, 0, 0]
21i=2, j=9: [1, 1{(1)}, 0, 1{(3)}, 1{(3,1)}, 0, 0, 0, 0, 0, 0]
22i=2, j=8: [1, 1{(1)}, 0, 1{(3)}, 1{(3,1)}, 0, 0, 0, 1{(3,1,4)}, 0, 0]
23i=2, j=7: [1, 1{(1)}, 0, 1{(3)}, 1{(3,1)}, 0, 0, 1{(3,4)}, 1{(3,1,4)}, 0, 0]
24i=2, j=6: [1, 1{(1)}, 0, 1{(3)}, 1{(3,1)}, 0, 0, 1{(3,4)}, 1{(3,1,4)}, 0, 0]
25i=2, j=5: [1, 1{(1)}, 0, 1{(3)}, 1{(3,1)}, 1{(1,4)}, 0, 1{(3,4)}, 1{(3,1,4)}, 0, 0]
26i=2, j=4: [1, 1{(1)}, 0, 1{(3)}, 2{(3,1),(4)}, 1{(1,4)}, 0, 1{(3,4)}, 1{(3,1,4)}, 0, 0]
27i=3, j=10: [1, 1{(1)}, 0, 1{(3)}, 2{(3,1),(4)}, 1{(1,4)}, 0, 1{(3,4)}, 1{(3,1,4)}, 0, 1{(3,1,4,2)}]
28i=3, j=9: [1, 1{(1)}, 0, 1{(3)}, 2{(3,1),(4)}, 1{(1,4)}, 0, 1{(3,4)}, 1{(3,1,4)}, 1{(3,4,2)}, 1{(3,1,4,2)}]
29i=3, j=8: [1, 1{(1)}, 0, 1{(3)}, 2{(3,1),(4)}, 1{(1,4)}, 0, 1{(3,4)}, 1{(3,1,4)}, 1{(3,4,2)}, 1{(3,1,4,2)}]
30i=3, j=7: [1, 1{(1)}, 0, 1{(3)}, 2{(3,1),(4)}, 1{(1,4)}, 0, 2{(3,4),(1,4,2)}, 1{(3,1,4)}, 1{(3,4,2)}, 1{(3,1,4,2)}]
31i=3, j=6: [1, 1{(1)}, 0, 1{(3)}, 2{(3,1),(4)}, 1{(1,4)}, 2{(3,1,2),(4,2)}, 2{(3,4),(1,4,2)}, 1{(3,1,4)}, 1{(3,4,2)}, 1{(3,1,4,2)}]
32i=3, j=5: [1, 1{(1)}, 0, 1{(3)}, 2{(3,1),(4)}, 2{(1,4),(3,2)}, 2{(3,1,2),(4,2)}, 2{(3,4),(1,4,2)}, 1{(3,1,4)}, 1{(3,4,2)}, 1{(3,1,4,2)}]
33i=3, j=4: [1, 1{(1)}, 0, 1{(3)}, 2{(3,1),(4)}, 2{(1,4),(3,2)}, 2{(3,1,2),(4,2)}, 2{(3,4),(1,4,2)}, 1{(3,1,4)}, 1{(3,4,2)}, 1{(3,1,4,2)}]
34i=3, j=3: [1, 1{(1)}, 0, 2{(3),(1,2)}, 2{(3,1),(4)}, 2{(1,4),(3,2)}, 2{(3,1,2),(4,2)}, 2{(3,4),(1,4,2)}, 1{(3,1,4)}, 1{(3,4,2)}, 1{(3,1,4,2)}]
35i=3, j=2: [1, 1{(1)}, 1{(2)}, 2{(3),(1,2)}, 2{(3,1),(4)}, 2{(1,4),(3,2)}, 2{(3,1,2),(4,2)}, 2{(3,4),(1,4,2)}, 1{(3,1,4)}, 1{(3,4,2)}, 1{(3,1,4,2)}]
36i=4, j=10: [1, 1{(1)}, 1{(2)}, 2{(3),(1,2)}, 2{(3,1),(4)}, 2{(1,4),(3,2)}, 2{(3,1,2),(4,2)}, 2{(3,4),(1,4,2)}, 1{(3,1,4)}, 1{(3,4,2)}, 3{(3,1,4,2),(1,4,5),(3,2,5)}]
37i=4, j=9: [1, 1{(1)}, 1{(2)}, 2{(3),(1,2)}, 2{(3,1),(4)}, 2{(1,4),(3,2)}, 2{(3,1,2),(4,2)}, 2{(3,4),(1,4,2)}, 1{(3,1,4)}, 3{(3,4,2),(3,1,5),(4,5)}, 3{(3,1,4,2),(1,4,5),(3,2,5)}]
38i=4, j=8: [1, 1{(1)}, 1{(2)}, 2{(3),(1,2)}, 2{(3,1),(4)}, 2{(1,4),(3,2)}, 2{(3,1,2),(4,2)}, 2{(3,4),(1,4,2)}, 3{(3,1,4),(3,5),(1,2,5)}, 3{(3,4,2),(3,1,5),(4,5)}, 3{(3,1,4,2),(1,4,5),(3,2,5)}]
39i=4, j=7: [1, 1{(1)}, 1{(2)}, 2{(3),(1,2)}, 2{(3,1),(4)}, 2{(1,4),(3,2)}, 2{(3,1,2),(4,2)}, 3{(3,4),(1,4,2),(2,5)}, 3{(3,1,4),(3,5),(1,2,5)}, 3{(3,4,2),(3,1,5),(4,5)}, 3{(3,1,4,2),(1,4,5),(3,2,5)}]
40i=4, j=6: [1, 1{(1)}, 1{(2)}, 2{(3),(1,2)}, 2{(3,1),(4)}, 2{(1,4),(3,2)}, 3{(3,1,2),(4,2),(1,5)}, 3{(3,4),(1,4,2),(2,5)}, 3{(3,1,4),(3,5),(1,2,5)}, 3{(3,4,2),(3,1,5),(4,5)}, 3{(3,1,4,2),(1,4,5),(3,2,5)}]
41i=4, j=5: [1, 1{(1)}, 1{(2)}, 2{(3),(1,2)}, 2{(3,1),(4)}, 3{(1,4),(3,2),(5)}, 3{(3,1,2),(4,2),(1,5)}, 3{(3,4),(1,4,2),(2,5)}, 3{(3,1,4),(3,5),(1,2,5)}, 3{(3,4,2),(3,1,5),(4,5)}, 3{(3,1,4,2),(1,4,5),(3,2,5)}]
42結果:3{(3,1,4,2),(1,4,5),(3,2,5)}