#codeifyoucansolve
Given a list of n integers, A={a1,a2,…,an}, and another integer, k representing the expected sum. Select zero or more numbers from A such that the sum of these numbers is as near as possible, but not exceeding, to the expected sum (k).

Note

Each element of A can be selected multiple times.
If no element is selected then the sum is 0.
Input Format

The first line contains T the number of test cases.
Each test case comprises of two lines. First line contains two integers, n k, representing the length of list A and expected sum, respectively. Second line consists of n space separated integers, a1,a2,…,an, representing the elements of list A.

Constraints
1≤T≤10
1≤n≤2000
1≤k≤2000
1≤ai≤2000,where i∈[1,n]
Output Format

Output T lines, the answer for each test case.

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

Copyright (c) 2015 HackerRank.
All Rights Reserved
Suggest Edits
984 hackers have submitted code
Share
………..

#include
int knapsack(int K,int w[],int v[],int n)
{
int i,k;
int t[n+1][K+1];
for(i=0;i<=n;i++)
{
for(k=0;k<=K;k++)
{
if(i==0||k==0)
t[i][k]=0;
else if(w[i-1]t[i-1][k])
{
t[i][k] = w[i-1]+t[i-1][k-w[i-1]];
}
else
{
t[i][k] = t[i-1][k];
}
}
else
t[i][k]=t[i-1][k];
}
}
return t[n][K];
}
int main() {
int T,N,n,K,num;
int w[2000],v[2000];
int k,j,i;
scanf(“%d”,&T);
while(T–)
{
scanf(“%d%d”,&N,&K);
i=N;
k=0;
while(i–)
{
j=1;
n=K;
scanf(“%d”,&num);
while(n)
{
v[k]=j;
w[k]=num*j;
k=k+1;
j=j+1;
n=K/(num*j);
}
}
printf(“%d\n”,knapsack(K,w,v,k));
/*for(j=0;j<k;j++)
{
printf("%d %d\n",w[j],v[j]);
}*/
}
return 0;
}

Compiled & Run

http://ideone.com/4Ql8dB
https://twitter.com/codeifucansolve