HackerRank Knapsack problem solution

In this HackerRank Knapsack problem solution we have 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.

Function Description

Complete the unboundedKnapsack function in the editor below. It must return an integer that represents the sum nearest to without exceeding the target value.

unboundedKnapsack has the following parameter(s):

• k: an integer
• arr: an array of integers

HackerRank Knapsack problem solution in Python.

T = int(input())
for case in range(T):
    N,K = map(int,input().rstrip().split(' '))
    A = list(map(int,input().rstrip().split(' ')))
    dp = [False]*(K+1)
    dp[0] = True
    for c in A:
        for i in range(c,len(dp)):
            dp[i] |= dp[i-c]
    print(max(i for i in range(len(dp)) if dp[i]))
        
    

Knapsack problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for(int ii=0;ii<t;ii++){
            int n = sc.nextInt();
            int k = sc.nextInt();
            int arr[] = new int[n];
            for(int i=0;i<n;i++)
                arr[i] = sc.nextInt();
            int w[] = new int[k+1];
            for(int i=0;i<n;i++){
                for(int j=arr[i];j<=k;j++){
                    w[j] = Math.max(w[j],arr[i]+w[j-arr[i]]);
                }
            }
            System.out.println(w[k]);
        }
    }
}

Problem solution in C++.

#include <bits/stdc++.h>
using namespace std;
vector <int> c; int dp[2005]; 
int main()
{
    int tc; cin >> tc;
    for (int g=0;g<tc; g++){c.clear(); memset(dp,0,sizeof(dp)); 
    int a,b; cin >> a >> b;
    for (int g=0;g<a; g++)
    {
    int d; cin >> d; c.push_back(d); 
    }sort(c.begin(), c.end());
    for (int g=1;g<=b; g++)
    {
        for (int y=0;y<c.size(); y++)
        {
            if (c[y]>g) continue;
            dp[g]=max(dp[g], c[y]+dp[g-c[y]]); 
        }
    }
    cout << dp[b] << 'n';} return 0; 
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
    int t,n,k,i,j,p;
    scanf("%d",&t);  
    while(t--)
        {
        scanf("%d %d",&n,&k);
        int a[n],dp[2001]={0};
        
        for(i=0;i<n;i++)
            {
            scanf("%d",&a[i]);
            dp[a[i]]=1;
        }
        
        for(i=1;i<=k;i++)
            for(j=0;j<n;j++)
                if(i-a[j]>0)
                    if(dp[i-a[j]]==1)
                      dp[i]=1;
           for(i=k;i>=1;i--)
               if(dp[i]==1)
                  break;
            printf("%dn",i);
    }
    
    return 0;
}