LeetCode Day동적 프로그래밍 3부

0-1 가방 문제

주제 설명

Ming은 자신의 최신 연구를 발표하기 위해 중요한 국제 과학 회의에 참석해야 하는 과학자입니다. 그는 몇 가지 연구 자료를 가져가야 하는데 여행 가방에 넣을 공간이 제한되어 있습니다. 이러한 연구 자료에는 실험 장비, 문헌, 실험 샘플 등이 포함되며, 각각은 서로 다른 공간을 차지하고 서로 다른 가치를 갖습니다.

밍의 짐 공간은 N입니다. 밍에게 가장 가치 있는 연구 자료를 어떻게 운반해야 하는지 물어보세요. 각 연구자료는 한 번만 선택할 수 있으며, 선택은 선택/선택 안함, 자르기는 불가능합니다.

입력 설명
첫 번째 줄에는 두 개의 양의 정수가 포함되어 있으며, 첫 번째 정수 M은 연구 자료의 유형을 나타내고 두 번째 양의 정수 N은 Ming의 수하물 공간을 나타냅니다.

두 번째 줄에는 각 유형의 연구 자료가 차지하는 공간을 나타내는 M개의 양의 정수가 포함되어 있습니다.

세 번째 행에는 각 연구 자료의 가치를 나타내는 M개의 양의 정수가 포함됩니다.

출력 설명
밍이 가지고 다닐 수 있는 연구자료의 최대 가치를 나타내는 정수를 출력합니다.

입력 예시
6 1
2 2 3 1 5 2
2 3 1 5 4 3

출력 예시
5

힌트
밍은 연구 재료 6개를 들고 다닐 수 있지만, 짐 공간은 1개에 불과하고, 1개 공간을 차지하는 연구 재료는 5의 가치가 있으므로 최종 답은 5가 출력됩니다.

데이터 범위:
1 1 연구자료가 차지하는 공간과 연구자료의 가치가 모두 1000 이하입니다.

public class Main{
    public static void main (String[] args) {
    /* code */
    Scanner s = new Scanner(System.in);

        int M = s.nextInt();
        int N = s.nextInt();
        // clear buffer symbol /n
        s.nextLine();

    String w = s.nextLine();
    String v = s.nextLine();

    int[] weight = Arrays.stream(w.split(" "))
                        .mapToInt(Integer::valueOf)
                        .toArray();
    int[] value = Arrays.stream(v.split(" "))
                        .mapToInt(Integer::valueOf)
                        .toArray();

    int[][] dp = new int[M][N+1];


    for(int i=weight[0]; i<=N; i++){
        dp[0][i] = value[0];
    }

    for(int i=1; i<M; i++){
        for(int j=1; j<=N; j++){
            if(weight[i] > j){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }

        }
    }

    System.out.println(dp[M-1][N]);
    }
}

1, dp 배열은 항목 i와 대상 가방 크기 j의 최대값을 얻을 수 있음을 의미합니다. 행은 품목을 나타내고 열은 가방의 크기를 나타냅니다.

2, init의 경우 첫 번째 행과 첫 번째 열을 초기화합니다(그러나 실제로는 기본적으로 0으로 열을 초기화합니다. 즉)

3, 회귀 관계는 다음과 같습니다: 각 항목에 대해:
a, 상품의 무게가 가방 사이즈보다 무거울 경우 해당 상품을 선택할 수 없으며, 현재 사이즈는 이전에 선택한 상품들의 컬렉션 사이즈입니다.
b, 항목의 무게가 괜찮다면 이전에 선택한 항목의 컬렉션 크기에서 현재 항목의 크기를 뺀 크기를 비교해야 합니다(그렇지 않으면 전체 크기는 크기 + 크기가 됩니다). 현재 항목의 경우 dp 배열의 논리가 중단됩니다.

2차원 배열을 사용하여 모든 결과를 기록하고 이전 행에서 현재 행을 검색할 수 있으므로 이중 루프의 순서는 다음과 같습니다.

또한 이를 실현하기 위해 1차원 배열을 사용할 수도 있습니다.

    for(int i=1; i<M; i++){
        for(int j=1; j<=N; j++){
            if(weight[i] > j){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }

로 변경

        int[] dp = new int[target+1];

        for(int i=1; i<nums.length; i++){
            for(int j=target; j>=1; j--){
                if(nums[i] > j){
                    continue;
                }
                dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);    
            }
        }

416. 파티션 동일 하위 집합 합계

정수 배열 nums가 주어졌을 때 배열을 두 개의 하위 집합으로 분할하여 두 하위 집합의 요소 합계가 같으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

예 1:

입력: 숫자 = [1,5,11,5]
출력: true
설명: 배열은 [1, 5, 5] 및 [11]로 분할될 수 있습니다.
예시 2:

입력: 숫자 = [1,2,3,5]
출력: 거짓
설명: 배열을 동일한 합계 하위 집합으로 분할할 수 없습니다.

제약사항:

1 <= nums.length <= 200
1 <= 숫자[i] <= 100
원본페이지

    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if(sum%2==1){
            return false;
        }
        int target = sum>>1;
        int[][] dp = new int[nums.length][target+1];

        for(int i=nums[0]; i<=target; i++){
            dp[0][i] = nums[0];
        }

        for(int i=1; i j){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i]);
                }     
            }
        }

        return dp[nums.length-1][target] == target;  
    }





          

            
        
위 내용은 LeetCode Day동적 프로그래밍 3부의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!