[go: up one dir, main page]
Scribd
Upload
19 views2 pages

Experiment 2.2: Student Name: Harsh Kumar Singh UID: 21BCS11624 Section/Group: 608-B

The document describes an experiment to implement the subset sum problem using dynamic programming. It includes the aim, objectives, procedure/algorithm, and observations. The procedure uses a 2D vector dp to store boolean values representing whether a subset sum is possible at each index. Two for loops iterate through dp to calculate values in bottom-up fashion. The time complexity is O(sum*n) where sum is the target sum and n is the array size. The learning outcomes are understanding dynamic programming concepts and developing algorithmic problem-solving abilities.

Uploaded by

Ashish Goswami
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
19 views2 pages

Experiment 2.2: Student Name: Harsh Kumar Singh UID: 21BCS11624 Section/Group: 608-B

The document describes an experiment to implement the subset sum problem using dynamic programming. It includes the aim, objectives, procedure/algorithm, and observations. The procedure uses a 2D vector dp to store boolean values representing whether a subset sum is possible at each index. Two for loops iterate through dp to calculate values in bottom-up fashion. The time complexity is O(sum*n) where sum is the target sum and n is the array size. The learning outcomes are understanding dynamic programming concepts and developing algorithmic problem-solving abilities.

Uploaded by

Ashish Goswami
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Course Name: DAA Lab Course Code: 21ITH-311/21CSH-311

Experiment 2.2
Student Name: Harsh Kumar Singh UID: 21BCS11624
Branch: BE-CSE Section/Group: 608-B
Semester: 5th Date of Performance: 05-10-2023
Subject Name: DAA Lab Subject Code: 21CSH-311

Aim: Develop a program and analyze complexity to implement subset-sum problem using Dynamic.

Objectives: Objective is to implement subset-sum problem using Dynamic programming.

Procedure/Algorithm:

#include <iostream>
#include <vector>
using namespace std;

bool isSubsetSum(vector<int>& nums, int targetSum) {


int n = nums.size();
vector<vector<bool>> dp(n + 1, vector<bool>(targetSum + 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 <= targetSum; j++) {
if (j < nums[i - 1])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
}
}

return dp[n][targetSum];
}

int main() {
vector<int> nums = {3, 34, 4, 12, 5, 2};
int targetSum = 15;
Course Name: DAA Lab Course Code: 21ITH-311/21CSH-311
if (isSubsetSum(nums, targetSum))
cout << "Found a subset with given sum." << endl;
else
cout << "No subset found with given sum." << endl;

return 0;
}

Observations/Outcome:

Time Complexity: O(sum*n), where sum is the ‘target sum’ and ‘n’ is the size of array.

Learning Outcome:

1) Demonstrates understanding of dynamic programming concepts, including problem decomposition and


memorization using a 2D array.
2) Develops algorithmic thinking and problem-solving abilities by successfully implementing a solution to
the Subset Sum problem, applying skills to similar challenges.

You might also like