Java-Competitive-Programming/Algorithms/Knapsack.java at threads · joney000/Java-Competitive-Programming · GitHub

History

executable file

59 lines (44 loc) · 1.34 KB

Raw

/* package joney_000 */

import java.util.*;

import java.lang.*;

import java.io.*;

import java.math.*;

class Knapsack

{

public static long ans=0;

public static void main(String[] args)throws Exception

{

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

BufferedWriter out=new BufferedWriter(new OutputStreamWriter(System.out));

ans=0;

int tests=Integer.parseInt(br.readLine());

for(int t=0;t<tests;t++){

int n=Integer.parseInt(br.readLine());

int W=Integer.parseInt(br.readLine());

int val[]=new int[n];

String[] s=br.readLine().split(" ");

for(int i=0;i<n;i++){

val[i]=Integer.parseInt(s[i]);

}

int wt[]=new int[n];

s=br.readLine().split(" ");

for(int i=0;i<n;i++){

wt[i]=Integer.parseInt(s[i]);

}

int[][] dp=new int[n+1][W+1];

for(int i=0;i<=n;i++)dp[i][0]=0;

for(int i=0;i<=W;i++)dp[0][i]=0;

for(int i=1;i<=n;i++){

for(int j=1;j<=W;j++){

if(wt[i-1]<=j){

dp[i][j]=Math.max(dp[i-1][j],val[i-1]+dp[i-1][j-wt[i-1]]);

}else{

dp[i][j]=dp[i-1][j];

}

ans=dp[n][W];

out.write(""+ans+"\n");out.flush();

}

Java-Competitive-Programming/Algorithms/Knapsack.java at threads · joney000/Java-Competitive-Programming · GitHub

Expand file tree

Breadcrumbs

Knapsack.java

Latest commit

History

Breadcrumbs

Knapsack.java

File metadata and controls