Scribd Logo
Upload

Welcome to Scribd!

  • 18 views

    Kamal Rohilla 2K18/CO/166 ADA Assignment 13 Apr. 2020

    Uploaded by

    kamal
    The document contains code for 3 algorithms - coin change combination, longest increasing subsequence, and subset sum. It provides the code to implement each algorithm, taking input from the user and outputting the result. For each algorithm, it includes the code, takes input like array size and values, runs the algorithm function on the input, and prints the output.

    Copyright:

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

    Kamal Rohilla 2K18/CO/166 ADA Assignment 13 Apr. 2020

    Uploaded by

    kamal
    18 views10 pages
    The document contains code for 3 algorithms - coin change combination, longest increasing subsequence, and subset sum. It provides the code to implement each algorithm, taking input from the user and outputting the result. For each algorithm, it includes the code, takes input like array size and values, runs the algorithm function on the input, and prints the output.

    Original Title

    os_lab

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document contains code for 3 algorithms - coin change combination, longest increasing subsequence, and subset sum. It provides the code to implement each algorithm, taking input from the user and outputting the result. For each algorithm, it includes the code, takes input like array size and values, runs the algorithm function on the input, and prints the output.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    18 views10 pages

    Kamal Rohilla 2K18/CO/166 ADA Assignment 13 Apr. 2020

    Uploaded by

    kamal
    The document contains code for 3 algorithms - coin change combination, longest increasing subsequence, and subset sum. It provides the code to implement each algorithm, taking input from the user and outputting the result. For each algorithm, it includes the code, takes input like array size and values, runs the algorithm function on the input, and prints the output.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 10

    KAMAL

    ROHILLA
    2K18/CO/166
    ADA
    ASSIGNMENT
    13 Apr. 2020
    1. COIN CHANGE
    #include<iostream>
    #include<bits/stdc++.h>
    using namespace std;
    int coinChangeCombi(vector<int> &coins, int tar)
    {
    vector<int> dp(tar + 1, 0);
    dp[0] = 1;

    for (int c = 0; c < coins.size(); c++)


    {
    for (int t = 1; t <= tar; t++)
    {
    if (t - coins[c] >= 0)
    dp[t] += dp[t - coins[c]];
    }
    }
    return dp[tar];
    }
    int main()
    {
    int n;
    cout<<"Enter the number of types of currency
    coins:\n";
    cin>>n;
    vector<int>coins(n);
    cout<<"\nEnter the coins:\n";
    for(int i=0;i<n;i++)
    cin>>coins[i];
    cout<<"\nEnter the sum you want to make change
    for:";
    int sum;
    cin>>sum;
    int ans=coinChangeCombi(coins,sum);
    cout<<"\nThe total number of ways to get
    "<<sum<<" as sum taking coins from given array are
    "<<ans<<endl;
    return 0;

    OUTPUT:
    2. LIS
    #include<iostream>
    #include<bits/stdc++.h>
    using namespace std;
    int LIS(vector<int> &arr)
    {
    vector<int> dp(arr.size(), 1);
    int max_ = 1;
    for (int i = 1; i < arr.size(); i++)
    {
    for (int j = 0; j < i; j++)
    {
    if (arr[i] > arr[j] && dp[j] + 1 > dp[i])
    {
    dp[i] = dp[j] + 1;
    max_ = max(max_, dp[i]);
    }
    }
    }
    return max_;
    }

    int main()
    {
    int n;
    cout<<"Enter the size of array\n";
    cin>>n;
    vector<int>arr(n);
    cout<<"\nEnter the "<<n<<" values in array\n";
    for(int i=0;i<n;i++)
    cin>>arr[i];

    int ans=LIS(arr);
    cout<<"The length of longest increasing
    subsequence in given array is "<<ans<<endl;
    return 0;

    }
    OUTPUT:
    3. SUBSET SUM
    #include<bits/stdc++.h>
    using namespace std;

    bool isSubsetSum(int arr[], int n, int sum)


    {

    bool subset[n+1][sum+1];
    for (int i = 0; i <= n; i++)
    subset[i][0] = true;
    for (int i = 1; i <= sum; i++)
    subset[0][i] = false;
    for (int i = 1; i <= n; i++)
    {
    for (int j = 1; j <= sum; j++)
    {
    if(j<arr[i-1])
    subset[i][j] = subset[i-1][j];
    if (j >= arr[i-1])
    subset[i][j] = subset[i-1][j] ||
    subset[i - 1][j-arr[i-
    1]];
    }
    }

    return subset[n][sum];
    }
    int main()
    {
    int n;
    cout<<"Enter the size of array\n";
    cin>>n;
    int arr[n];
    cout<<"Enter the values in array\n";
    for(int i=0;i<n;i++)cin>>arr[i];
    cout<<"Enter the sum\n";
    int sum;
    cin>>sum;
    if (isSubsetSum(arr, n, sum) == true)
    printf("Found a subset with given sum");
    else
    printf("No subset with given sum");
    return 0;
    }
    OUTPUT:

    ------------------------END---------------------------------------

    You might also like