ปัญหาผลรวมย่อยในช่องว่าง O (sum)


ระดับความยาก กลาง
ถามบ่อยใน อะโดบี อเมซอน ดริชติ - ซอฟท์
แถว การเขียนโปรแกรมแบบไดนามิก

คำชี้แจงปัญหา

ปัญหา "ผลรวมย่อยในพื้นที่ O (ผลรวม)" ระบุว่าคุณได้รับอาร์เรย์ของจำนวนเต็มที่ไม่ใช่จำนวนเต็มและค่าเฉพาะ ตอนนี้ดูว่ามีเซตย่อยที่มีผลรวมเท่ากับค่าอินพุตที่กำหนดหรือไม่

ตัวอย่าง

Array = {1, 2, 3, 4}
targetSum = 7
The subset having sum equal to given input is possible

ปัญหาผลรวมย่อยในช่องว่าง O (sum)

แนวทางสำหรับปัญหา Subset Sum ในช่องว่าง O (sum)

แนวทางที่ง่ายที่สุดที่ใคร ๆ ก็คิดได้คือการสร้างชุดย่อยทั้งหมดและหาผลรวม ตอนนี้ตรวจสอบว่าผลรวมนี้เท่ากับผลรวมอินพุตที่กำหนดใช่ไหม? แนวทางนั้นถูกต้อง ไม่ต้องสงสัยเลยว่า แต่มีปัญหาอย่างหนึ่งคือเราไม่สามารถสร้างชุดย่อยทั้งหมดได้อย่างมีประสิทธิภาพ การสร้างส่วนย่อยเองมีความซับซ้อนของเวลา O (2 ^ N) ดังนั้นเราต้องคิดหาวิธีอื่นที่มีประสิทธิภาพในการแก้ปัญหา

เอาล่ะลองคิดปัญหานี้ด้วยวิธีนี้ เรารู้ว่ามีเซตย่อยบางส่วนที่มีผลรวมบางส่วน ตอนนี้สำหรับองค์ประกอบปัจจุบันเรามีสองตัวเลือกไม่ว่าเราจะเพิ่มลงในชุดย่อยที่มีอยู่แล้วหรือเราจะไม่โฆษณาลงในส่วนย่อย ตอนนี้เรารู้แล้วว่าเราต้องทำอะไร ในการสรุปเราจะเรียกใช้การวนซ้ำบนผลรวม (ซึ่งอยู่บนค่าตั้งแต่ 1 ถึงผลรวมอินพุต) เนื่องจากสิ่งนี้เริ่มสับสนเล็กน้อย เราเรียกผลรวมอินพุตว่า "เป้าหมาย" และผลรวมที่ต้องสำรวจ เราจะเป็นตัวแทนของพวกเขาด้วย“ i” และสำหรับแต่ละ i เราตรวจสอบว่าไม่ใช้องค์ประกอบปัจจุบันหรือไม่“ เรามีเซตย่อยที่มีผลรวมเท่ากับ i หรือไม่” หรือถ้าเราใช้องค์ประกอบปัจจุบันนี้เราสามารถทำผลรวมได้เท่ากับของ i? เราจึงเรียบเรียงประโยคสุดท้ายนี้ใหม่ได้ ถ้าเราลบค่าขององค์ประกอบปัจจุบันออกจาก i เรามีส่วนย่อยที่มีผลรวมเท่ากับขององค์ประกอบ i-current หรือไม่?

ดังนั้นตอนนี้เราต้องหาว่าเราสามารถสร้างเซตย่อยที่มีผลรวมเท่ากับ i หรือเท่ากับองค์ประกอบ i-current ได้หรือไม่

ทีนี้จะแก้ยังไง? เราจะใช้ การเขียนโปรแกรมแบบไดนามิก เพื่อแก้ปัญหานี้ เราจะสร้างอาร์เรย์ 2 มิติหรือเมทริกที่มีเซลล์ [i, j] เป็นจริงถ้าเราได้เซตย่อยที่มีผลรวมเท่ากับ j โดยใช้องค์ประกอบตั้งแต่ 0 ถึง i มิฉะนั้นจะเป็นเท็จ

สูตรซ้ำ

dp[i][j] = dp[i-1][j] | dp[i-1][j-input[i]]

จากสูตรการเรียกซ้ำเราจะได้ทราบว่าแถวปัจจุบันขึ้นอยู่กับแถวสุดท้ายเท่านั้น ดังนั้นเราจึงสามารถหลีกเลี่ยงการเก็บเพียงสองแถวแทนที่จะเป็น n แถวสำหรับ n องค์ประกอบ แถวหนึ่งจะทำหน้าที่เหมือนแถวสำหรับองค์ประกอบสุดท้ายและอีกแถวสำหรับองค์ประกอบปัจจุบัน นี่คือการเพิ่มประสิทธิภาพ DP ที่รู้จักกันดี

รหัส

รหัส C ++ สำหรับ Subset Sum Problem ในช่องว่าง O (sum)

#include<bits/stdc++.h>
using namespace std;

#include <stdio.h>
#include <stdbool.h>

bool findSubset(int arr[], int n, int targetSum)
{
  // dp array to store if any sum is possible
  bool dp[2][targetSum + 1];

  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= targetSum; j++) {

      // subset with sum equal to zero is always possible
      // we don't choose any element
      if (j == 0)
        dp[i % 2][j] = true;
      // j != 0 and i ==0
      else if (i == 0)
        dp[i % 2][j] = false;
      // current element is greater than the current value of sum(j)
      // so take OR of two conditions
      // 1. Take the current element check if we can get a subset having sum = j-arr[i-1]
      // 2. We don't take the current element
      else if (arr[i - 1] <= j)
        dp[i % 2][j] = dp[(i + 1) % 2][j - arr[i - 1]] || dp[(i + 1) % 2][j];
      // Here we cannot take the current element
      // So simply check is such a subset is possible
      else
        dp[i % 2][j] = dp[(i + 1) % 2][j];
    }
  }

  return dp[n % 2][targetSum];
}

int main(){
  // Number of elements
  int n;cin>>n;
  // array to store non-negative numbers
  int a[n];
  for(int i=0;i<n;i++)
    cin>>a[i];
  int targetSum;
  cin>>targetSum;
  bool can = findSubset(a, n, targetSum);
  if(can == true)
    cout<<"The subset having sum equal to given input is possible";
  else
    cout<<"None of the subsets have sum equal to given input";
}
4
1 2 3 4
6
The subset having sum equal to given input is possible

โค้ด Java สำหรับ Subset Sum Problem ในช่องว่าง O (sum)

import java.util.*;

class Main{
  
  static boolean findSubset(int arr[], int n, int targetSum) 
  { 
    // dp array to store if any sum is possible
    boolean dp[][] = new boolean[2][targetSum + 1];

    for (int i = 0; i <= n; i++) { 
      for (int j = 0; j <= targetSum; j++) { 

        // subset with sum equal to zero is always possibe
        // we don't choose any element
        if (j == 0) 
          dp[i % 2][j] = true; 
        // j != 0 and i ==0
        else if (i == 0) 
          dp[i % 2][j] = false;
        // current element is greater than the current value of sum(j)
        // so take OR of two conditions
        // 1. Take the current element check if we can get a subset having sum = j-arr[i-1]
        // 2. We don't take the current element
        else if (arr[i - 1] <= j) 
          dp[i % 2][j] = dp[(i + 1) % 2][j - arr[i - 1]] || dp[(i + 1) % 2][j]; 
        // Here we cannot take the current element
        // So simply check is such a subset is possible
        else
          dp[i % 2][j] = dp[(i + 1) % 2][j]; 
      } 
    }

    return dp[n % 2][targetSum]; 
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);

    // Number of elements
    int n = sc.nextInt();
    // array to store non-negative numbers
    int a[] = new int[n];
    for(int i=0;i<n;i++)
      a[i] = sc.nextInt();
    int targetSum = sc.nextInt();
    boolean can = findSubset(a, n, targetSum);
    if(can == true)
      System.out.println("The subset having sum equal to given input is possible");
    else
      System.out.println("None of the subsets have sum equal to given input");
  }
}
4
1 2 3 4
6
The subset having sum equal to given input is possible

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

O (ผลรวม * N) เนื่องจากเราได้สำรวจองค์ประกอบทั้งหมดและตรวจสอบสำหรับแต่ละค่าของผลรวมจาก 0 ถึงผลรวมอินพุตที่กำหนดว่าเป็นไปได้หรือไม่? ดังนั้นความซับซ้อนของเวลาจึงเป็นพหุนาม

ความซับซ้อนของอวกาศ

O (ผลรวม) เนื่องจากเราไม่ได้ใช้แถวสำหรับแต่ละองค์ประกอบ แทนที่จะทำอย่างนั้นเราใช้เพียงแค่สองแถวในการจัดเก็บผลลัพธ์ระดับกลางสำหรับองค์ประกอบปัจจุบันและองค์ประกอบสุดท้าย ดังนั้นความซับซ้อนของอวกาศจึงเป็นเชิงเส้น