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.

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]))
        
    

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;
}