loading...

Daily HackerRank Challenge - Day 11

wingkwong profile image Wing-Kam ・3 min read

Daily HackerRank Challenge (30 Part Series)

1) Daily HackerRank Challenge - Day 0 2) Daily HackerRank Challenge - Day 1 3 ... 28 3) Daily HackerRank Challenge - Day 2 4) Daily HackerRank Challenge - Day 3 5) Daily HackerRank Challenge - Day 4 6) Daily HackerRank Challenge - Day 5 7) Daily HackerRank Challenge - Day 6 8) Daily HackerRank Challenge - Day 7 9) Daily HackerRank Challenge - Day 8 10) Daily HackerRank Challenge - Day 9 11) Daily HackerRank Challenge - Day 10 12) Daily HackerRank Challenge - Day 11 13) Daily HackerRank Challenge - Day 12 14) Daily HackerRank Challenge - Day 13 15) Daily HackerRank Challenge - Day 14 16) Daily HackerRank Challenge - Day 15 17) Daily HackerRank Challenge - Day 16 18) Daily HackerRank Challenge - Day 17 19) Daily HackerRank Challenge - Day 19 20) Daily HackerRank Challenge - Day 20 21) Daily HackerRank Challenge - Day 21 22) Daily HackerRank Challenge - Day 22 23) Daily HackerRank Challenge - Day 23 24) Daily HackerRank Challenge - Day 24 25) Daily HackerRank Challenge - Day 25 26) Daily HackerRank Challenge - Day 26 27) Daily HackerRank Challenge - Day 27 28) Daily HackerRank Challenge - Day 28 29) Daily HackerRank Challenge - Day 29 30) Daily HackerRank Challenge - Day 30

About

This is a series of Daily HackerRank Challenge. Each day I show the some solutions written in C++.


Knapsack

Given an array of integers and a target sum, determine the sum nearest to but not exceeding the target that can be created. To create the sum, use any element of your array zero or more times.

For example, if arr=[2,3,4] and your target sum is 10, you might select [2,2,2,2,2], [2,2,2,3] or [3,3,3,1] . In this case, you can arrive at exactly the target.

Sample Input

2
3 12
1 6 9
5 9
3 4 4 4 8

Sample Output

12
9

Explanation

In the first test case, one can pick {6, 6}. In the second, we can pick {3,3,3}.

This is a unbounded knapsack so we cannot use the classic way to solve this problem. To solve it, we can break the problem into smaller problems first.

If we put the first item into the knapsack, then the remaining capacity would be W-w1. So we can break it down to find out the maximum value max1 if we pack the same item N times in a knapsack of capacity W-w1. For the second item, we do the same thing to get max2 so that it has a remaining capacity of W-w2, and so on.

Each item has a own value now but we have to add the original value to it.

itemMax1 = max1 + v1

The maximum value is

W = max(itemMax1,itemMax2,...,itemMaxN)

where W is the maximum value packed in the knapsack of capacity.

Psuedo code

f(v[], w[], c) {
    // v: array of values
    // w: array of weights
    // c: capacity
    // n: length of the array

    // base case
    // if it is full, the total value of a 0 capacity knapsack is 0
    if(c==0) return 0;

    int[] m;

    // break it down to smaller problem
    // ----------------------------------------
    for(int i=0;i<n;i++){
        // if we can put item 1
        if(w[i]<c) m[i]=f(v,w,c-w[i]);
        // not enough space
        else m[i]=0; 
    }

    // add back the original value
    // ----------------------------------------
    for(int i=0;i<n;i++){
        // if we can put item 1
        if(w[i]<c) mm[i]=m[i] + v[i];
        // not enough space
        else mm[i]=0; 
    }

    // find the maximum value
    // ----------------------------------------
    int ans=mm[0];
    for(int i=1;i<n;i++){
        if(mm[i]>ans) ans=mm[i];
    }

    return ans;
}

However, we can use bottom-up dynamic programming solution for this problem to improve the above solution.

As we may see that we only have one parameter c for the recursive method where c ranges from W to 0 and v[] and w[] remain unchanged. Therefore, we can store the results computed by the recursive function in a 1d array.

int dp[W+1];

We can set our base case to 0.

dp[0] = 0;

We can turn

f(v,w,c-w[i]);

to

dp[c-w[i]]

Also from

int ans=mm[0];
for(int i=1;i<n;i++){
    if(mm[i]>ans) ans=mm[i];
}

return ans;

to

dp[c]=mm[0];
for(int i=1;i<n;i++){
    if(mm[i]>dp[c]) dp[c]=mm[i];
}

and the result would be

return dp[c];

So we have the following structure

dp[0] = 0

for C=0 ... W:
    for i=0 .. N:
        if w[i]<=C: 
            dp[i] = max ( dp[i], ( dp[C-w[i]] + v[i] ) )
        else 
            dp[i] = 0

In this question, there is no weight so we can consider weight is same as value.

Final Solution

int t,n,k;

void unboundedKnapsack(int n, int k, int a[]){
    int dp[k+1];
    memset(dp, 0, sizeof dp);
    FORN(i,0,k){
        REP(j,n){
            if(a[j]<=i) dp[i]=max(dp[i], dp[i-a[j]] + a[j]);
        }
    }
    cout << dp[k] << "\n";
}

int main()  
{ 
    FAST_INP;
    cin >> t;
    REP(i,t){
        cin >> n >> k;
        int a[n];
        REP(j,n) cin >> a[j];
        unboundedKnapsack(n,k,a);
    }
    return 0;
}

References:


Complete Code

Daily HackerRank Challenge (30 Part Series)

1) Daily HackerRank Challenge - Day 0 2) Daily HackerRank Challenge - Day 1 3 ... 28 3) Daily HackerRank Challenge - Day 2 4) Daily HackerRank Challenge - Day 3 5) Daily HackerRank Challenge - Day 4 6) Daily HackerRank Challenge - Day 5 7) Daily HackerRank Challenge - Day 6 8) Daily HackerRank Challenge - Day 7 9) Daily HackerRank Challenge - Day 8 10) Daily HackerRank Challenge - Day 9 11) Daily HackerRank Challenge - Day 10 12) Daily HackerRank Challenge - Day 11 13) Daily HackerRank Challenge - Day 12 14) Daily HackerRank Challenge - Day 13 15) Daily HackerRank Challenge - Day 14 16) Daily HackerRank Challenge - Day 15 17) Daily HackerRank Challenge - Day 16 18) Daily HackerRank Challenge - Day 17 19) Daily HackerRank Challenge - Day 19 20) Daily HackerRank Challenge - Day 20 21) Daily HackerRank Challenge - Day 21 22) Daily HackerRank Challenge - Day 22 23) Daily HackerRank Challenge - Day 23 24) Daily HackerRank Challenge - Day 24 25) Daily HackerRank Challenge - Day 25 26) Daily HackerRank Challenge - Day 26 27) Daily HackerRank Challenge - Day 27 28) Daily HackerRank Challenge - Day 28 29) Daily HackerRank Challenge - Day 29 30) Daily HackerRank Challenge - Day 30

Posted on Jul 5 by:

wingkwong profile

Wing-Kam

@wingkwong

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.

Discussion

markdown guide