Scribd Logo
Upload

Welcome to Scribd!

  • 4 views

    Arun Exp-6

    Uploaded by

    kumararunlamba89
    experiment 8 of DAA 5th sem in Chandigarh University

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Arun Exp-6

    Uploaded by

    kumararunlamba89
    4 views3 pages
    experiment 8 of DAA 5th sem in Chandigarh University

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    experiment 8 of DAA 5th sem in Chandigarh University

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    4 views3 pages

    Arun Exp-6

    Uploaded by

    kumararunlamba89
    experiment 8 of DAA 5th sem in Chandigarh University

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 3

    DEPARTMENT OF

    COMPUTER SCIENCE & ENGINEERING

    Experiment-6
    Student Name: Arun UID: 22BET10320
    Branch: IT Section/Group:22BET_IoT_703/B
    Semester: 5th Date of Performance: 10/09/2024
    Subject Name: DAA Subject Code: 22CSH-311

    1. Aim: Develop a program and analyze complexity to implement subset-sum


    problem using Dynamic Programming.

    2. Objective: The objective of this program is to determine whether a subset of a


    given set of integers sums to a specified value. This problem is a classic example
    of dynamic programming where we use a table to store intermediate results and
    build the solution incrementally.

    3. Implementation/Code:
    #include <iostream>
    #include <vector>
    using namespace std;
    void printSubsets(vector<int>& arr, vector<vector<bool>>& dp, int i, int j,
    vector<int>& subset) {
    if (j == 0) {
    cout << "{ ";
    for (int num : subset) {
    cout << num << " ";
    }
    cout << "}" << endl;
    return;
    }
    if (i == 0) return;
    if (dp[i-1][j]) {
    printSubsets(arr, dp, i-1, j, subset);
    }
    DEPARTMENT OF
    COMPUTER SCIENCE & ENGINEERING

    if (j >= arr[i-1] && dp[i-1][j - arr[i-1]]) {


    subset.push_back(arr[i-1]);
    printSubsets(arr, dp, i-1, j - arr[i-1], subset);
    subset.pop_back();
    }
    }
    bool subsetSum(vector<int>& arr, int sum) {
    int n = arr.size();
    vector<vector<bool>> dp(n + 1, vector<bool>(sum + 1, false));
    for (int i = 0; i <= n; ++i) {
    dp[i][0] = true;
    }
    for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= sum; ++j) {
    if (arr[i - 1] <= j) {
    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i - 1]];
    } else {
    dp[i][j] = dp[i - 1][j];
    }
    }
    }
    if (!dp[n][sum]) {
    return false;
    }
    vector<int> subset;
    cout << "Subsets with the given sum are:" << endl;
    printSubsets(arr, dp, n, sum, subset);
    return true;
    }
    DEPARTMENT OF
    COMPUTER SCIENCE & ENGINEERING

    int main() {
    vector<int> arr = {9, 44, 6, 64, 27, 6, 100};
    int sum = 100;

    if (!subsetSum(arr, sum)) {
    cout << "No subset with the given sum" << endl;
    }

    return 0;
    }
    4. Output:

    Fig1: Output for sum of subarray=100

    5. Time Complexity: O (n * sum) + O(2^n)


    6. Learning Outcomes:
    • Dynamic Programming concepts and how to apply them to solve problems.
    • The Subset Sum Problem and how to determine if a subset with a given sum
    exists within a set.
    • Improved understanding of two-dimensional arrays in C++ and how to use them
    for dynamic programming tables.

    You might also like