Knapsack

                            Solution in C :

In C++ :





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








In Java :





import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;

public class Solution {

	private static Scanner sc;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int i = 0; i < T; i++) {
			int n = sc.nextInt();
			int k = sc.nextInt();
			HashSet<Integer> map = new HashSet<Integer>();
			for (int j = 0; j < n; j++) {
				map.add(sc.nextInt());
			}
			System.out.println(getMultSum(map, k));
		}
	}

	private static int getMultSum(HashSet<Integer> map, int k) {
		Iterator<Integer> it = map.iterator();
		boolean[] sum = new boolean[k + 1];
		Arrays.fill(sum, false);
		sum[0] = true;
		int a = 0;
		for (int i = 0; i <= k; i++) {

			if (sum[i] == true) {
				it = map.iterator();
				while (it.hasNext()) {
					a = it.next();
					if ((i + a) <= k)
						sum[i + a] = true;
				}
			}
		}
		for(int i=k;i>=0;i--){
			if(sum[i] == true){
				return i;
			}
		}
		return 0;
	}
}








In C :





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

struct qnode
    {
    int data;
    struct qnode*next;
    
};

struct queue
    {
   struct qnode*front,*rear;
     
};

struct qnode*newnode(int k)
    {
    struct qnode*temp=(struct qnode*)malloc(sizeof(struct qnode));
    temp->data=k;
    temp->next=NULL;
    return temp;
    
};

struct queue*createque()
    {
    struct queue*q=(struct queue*)malloc(sizeof(struct queue));
    q->front=q->rear=NULL;
    return q;
};

void enqueue(struct queue*q,int k)
    {
    struct qnode*temp=newnode(k);
    if(q->front==NULL)
        {
        q->front =q->rear=temp;
    }
    else
        {
        q->rear->next=temp;
        q->rear=temp;
        
    }
}

int dequeue(struct queue*q)
    {
    if(q->front==NULL)
        return -1;
    int temp=q->front->data;
    q->front=q->front->next;
    if(q->front==NULL)
        q->rear=NULL;
    return temp;
    
}
    




int main() {

    int t;
    int n,k;
    int res,i,temp,temp2;
    int arr2[2003];int j,num;
    int *arr;
    int found,found1;
    scanf("%d",&t);
    while(t--)
        {
        for(i=0;i<2003;++i)
            arr2[i]=0;
        found=0;
        scanf("%d%d",&n,&k);
        temp=res=k;
        arr=(int*)malloc(n*sizeof(int));
        j=0;
        found1=0;
        for(i=0;i<n;++i)
        {
           
            
            scanf("%d",&num);
            if(k%num==0)
             {   found1=1;
              found=1;}   
            if(arr2[num]==0)
                {
                arr2[num]=1;
                arr[j]=num;
                j++;
            }
        }
        
        
        struct queue*q=createque();
        enqueue(q,k);
        while(((temp2=dequeue(q))!=-1) && found==0)
            {
           // printf("temp2=%d",temp2);
            for(i=0;i<j;++i)
                {
                temp=temp2-arr[i];
                
                if(temp<0)
                    continue;
                if(res>temp)
                    res=temp;
                
                if(res==0)
                {
                    found=1;
                    break;
                }
                else
                    enqueue(q,temp);
    
            }
        }
        
        if(found&&found1)
            printf("%d\n",k);
        
        else if(res==k)
            printf("0\n");
        else
        printf("%d\n",k-res);
            
        
        
        
    }
    
    return 0;
}








In Python3 :





t=int(input())
for _ in range(t):
    lst=[int(i) for i in input().split()]
    goal=lst[1]
    nums=[int(i) for i in input().split()]
    dyno=[0]
    dyno += [-1]*goal
    for i in range(len(dyno)):
        tmp=-1
        largest_x=-1
        val=0
        for x in nums:
            if i-x >= 0 and dyno[i-x]+x>=val:
                tmp=i-x
                largest_x=x
                val=dyno[i-x]+x
        if tmp<0:
            dyno[i]=0
        else:
            dyno[i]=largest_x+dyno[tmp]

    print(dyno[-1])