두 개의 정수 n과 m를 입력하여 0-n에서 임의로 몇 개의 수를 취하여 m와 같게 하다

프로그래밍은 두 개의 정수 n과 m를 입력하고 수열 1,2,3,...n에서 임의로 몇 개의 수를 취하여 m와 같게 한다.모든 가능한 조합을 열거할 것을 요구하다.사실은 배낭 문제야.해답 사고방식: 1.먼저 n>m이면 n에서 m보다 큰 수는 조합에 참여할 수 없다고 판단하고 이때 n=m를 설치한다.2. 최대수 n을 넣고 n==m를 넣으면 조건을 충족시키고 출력한다.3. n을 두 가지 상황으로 나누어 해답을 구한다. (1)n은 가입하지 않고 n=n-1을 취한다.m = m;차례로 내려가다.
(2)n 가입, n=n-1, m=m-n을 취하여 귀속한다
import java.util.*;

public class   {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();//n
            int sum = scanner.nextInt();//m
            findSum(sum, n);
            System.out.println(res);
            //System.out.println(count);
            //count = 0; // 
            res = new ArrayList<>();// res list
        }
    }

    private static List list = new ArrayList<>();
    private static List> res = new ArrayList<>();
    // private static int count = 0;// 

    public static void findSum(int sum, int n) {
        if (n < 1 || sum < 1)
            return;
        if (sum <= n) {// 
            list.add(sum); //  sum < n , sum 
            res.add(new LinkedList<>(list));
            list.remove(list.size() - 1);
            // count++;// 
            return;
        }
        list.add(n);
        findSum(sum - n, n - 1);// n , n=n-1,sum=sum-n
        list.remove(list.size() - 1);
        findSum(sum, n - 1);    // n , n=n-1,sum=sum
    }
}

좋은 웹페이지 즐겨찾기