パッケージ library.other

クラス DP

java.lang.Object
library.other.DP
public final class DP extends Object
DPを使った便利メソッドまとめ

  • コンストラクタの概要

    コンストラクタ
    コンストラクタ
    説明
    DP()
     

  • メソッドの概要

    修飾子とタイプ
    メソッド
    説明
    static final long
    knapsack(int[] a, long[] v, int w)
    個数制限なしナップサック 重さw_i, 価値v_iであるようなn種類の品物があり、重さの和がw以下となるように選ぶときの価値の最大値を求める
    static final long
    knapsack(int[] a, long[] v, int[] m, int w)
    個数制限つきナップザック 重さw_i, 価値v_iであるようなn種類の品物があり、i番目の品物はm_i個まで選ぶことができる 重さの和がw以下となるように選ぶときの価値の最大値を求める
    static final long
    knapsack(long[] a, int[] v, long[] m, long w)
    個数制限つきナップザック 重さw_i, 価値v_iであるようなn種類の品物があり、i番目の品物はm_i個まで選ぶことができる 重さの和がw以下となるように選ぶときの価値の最大値を求める
    static final long
    knapsack01(int[] a, long[] v, int w)
    01ナップザック 重さa_i, 価値v_iであるようなn個の品物があり、重さの和がw以下となるように選ぶときの価値の最大値を求める
    static final int
    knapsack01(long[] a, int[] v, long w)
    01ナップザック 重さw_i, 価値v_iであるようなn個の品物があり、重さの和がw以下となるように選ぶときの価値の最大値を求める
    static final int
    lcs(String s, String t)
    Longest Common Subsequence
    static final int[]
    lis(int[] a)
    最長増加部分列(Longest Increasing Subsequence)
    static final int[]
    lis(long[] a)
    最長増加部分列(Longest Increasing Subsequence)
    static final long
    maxRectangle(int[] a)
    ヒストグラムの最大長方形の面積を返す
    static final long
    maxRectangle(long[] a)
    ヒストグラムの最大長方形の面積を返す

    クラスから継承されたメソッド java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • コンストラクタの詳細

    • DP

      public DP()

  • メソッドの詳細

    • knapsack01

      public static final long knapsack01(int[] a, long[] v, int w)
      01ナップザック 重さa_i, 価値v_iであるようなn個の品物があり、重さの和がw以下となるように選ぶときの価値の最大値を求める
      パラメータ:
      a -
      v -
      w -
      戻り値:
      dpの最大値
      関連項目:

    • knapsack01

      public static final int knapsack01(long[] a, int[] v, long w)
      01ナップザック 重さw_i, 価値v_iであるようなn個の品物があり、重さの和がw以下となるように選ぶときの価値の最大値を求める
      パラメータ:
      a -
      v -
      w -
      戻り値:
      dpの最大値
      関連項目:

    • knapsack

      public static final long knapsack(int[] a, long[] v, int[] m, int w)
      個数制限つきナップザック 重さw_i, 価値v_iであるようなn種類の品物があり、i番目の品物はm_i個まで選ぶことができる 重さの和がw以下となるように選ぶときの価値の最大値を求める
      パラメータ:
      a -
      v -
      m -
      w -
      戻り値:
      dpの最大値
      関連項目:

    • knapsack

      public static final long knapsack(long[] a, int[] v, long[] m, long w)
      個数制限つきナップザック 重さw_i, 価値v_iであるようなn種類の品物があり、i番目の品物はm_i個まで選ぶことができる 重さの和がw以下となるように選ぶときの価値の最大値を求める
      パラメータ:
      a -
      v -
      m -
      w -
      戻り値:
      dpの最大値
      関連項目:

    • knapsack

      public static final long knapsack(int[] a, long[] v, int w)
      個数制限なしナップサック 重さw_i, 価値v_iであるようなn種類の品物があり、重さの和がw以下となるように選ぶときの価値の最大値を求める
      パラメータ:
      a -
      v -
      w -
      戻り値:
      dpの最大値
      関連項目:

    • maxRectangle

      public static final long maxRectangle(int[] a)
      ヒストグラムの最大長方形の面積を返す
      パラメータ:
      a -
      戻り値:
      ヒストグラムの最大長方形の面積
      関連項目:

    • maxRectangle

      public static final long maxRectangle(long[] a)
      ヒストグラムの最大長方形の面積を返す
      パラメータ:
      a -
      戻り値:
      ヒストグラムの最大長方形の面積
      関連項目:

    • lcs

      public static final int lcs(String s, String t)
      Longest Common Subsequence
      パラメータ:
      s -
      t -
      戻り値:
      最長共通部分列の長さ
      関連項目:

    • lis

      public static final int[] lis(int[] a)
      最長増加部分列(Longest Increasing Subsequence)
      パラメータ:
      a -
      戻り値:
      最長増加部分列
      関連項目:

    • lis

      public static final int[] lis(long[] a)
      最長増加部分列(Longest Increasing Subsequence)
      パラメータ:
      a -
      戻り値:
      最長増加部分列
      関連項目: