найти все наборы списка, которые добавляются к определенному яберу с динамическим программированием

Question

Я пытаюсь полностью понять динамическое программирование, поэтому я взял проблему с обычной суммой подмножества немного дальше, и я пытаюсь посмотреть, могу ли я распечатать все подмножества, добавляемые к определенному числу. На данный момент я сделал это рекурсивно, но я хотел бы выяснить, как это сделать динамически. Любая помощь приветствуется. Вот то, что я сейчас:

import java.util.ArrayList; 
import java.util.HashMap; 

import com.sun.xml.internal.bind.v2.schemagen.xmlschema.List; 



public class subsetSum { 

    public static void main (String[] args) { 
      ArrayList<Integer> list = new ArrayList<Integer>(); 
      list.add(1); 
      list.add(3); 
      list.add(4); 
      list.add(0); 
      printSublists(list, list, 4, true, 0); 
     } 

     public static Integer sum(ArrayList<Integer> list) { 
      Integer sum= 0; 
      for (Integer i:list) 
       sum = sum + i; 
      return sum; 
     } 

     public static void printSublists(ArrayList<Integer> list, ArrayList<Integer> list2, int n, boolean walkRight, int level) { 

      if (sum(list2) == n) 
      System.out.println(list2); 

      if (list2.size() == 1) 
      return; 

      if (walkRight) 
      printSublists(list, new ArrayList<Integer>(list2.subList(0, list2.size()-1)), n, walkRight, level+1); 

      walkRight = false; 

      printSublists(list, new ArrayList<Integer>(list2.subList(1, list2.size())), n, walkRight, level+1); 
     } 
} 

Answer 1

Шаг 1. Создание классов с помощью следующей доступной информации:

previousStateTransition: 
    previousSum 
    nextAddedElementIndex 
    countOfWaysHere 

sumState: 
    currentSum 
    countOfWaysHere 
    isInitial 
    previousStateTransitions (array of previousStateTransition objects ordered by nextAddedElementIndex) 

Шаг 2: Реализуйте алгоритм DP, заселение вышеуказанные объекты. (Это потребует HashMap отображения текущего значения к соответствующему sumState объекта

Шаг 3:. Реализуйте рекурсивную функцию, которая начинается с sumState объекта и находит все способы одержавшая там Будьте осторожны, как вы идете назад к. следить за nextAddedElementIndex и прекратить ходить previousSumTransitions когда достигнет или превысит последний элемент, который является частью текущей суммы.

Примечание оба объекта включают countOfWaysHere. в конце концов, sumState объекты имеют количество способов к этой окончательной окончательной сумме, в то время как объекты previousSumTransition позволяют узнать количество способов, которыми вы могли бы воспользоваться en до текущей суммы в течение первых k элементов.

Обязательно проверьте его!