fork download
copy 
  1. //package spoj;
  2.  
  3.  
  4. 				import java.util.Arrays;
  5. 				import java.io.*;
  6. 				class PARTY
  7. 				{
  8. 					public static void main(String args[])
  9. 					throws IOException
  10. 					{
  11. 						BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  12. 						PrintWriter pw=new PrintWriter(System.out);
  13. 						String str="";
  14. 						while(!(str=br.readLine().trim()).equals("0 0"))
  15. 						{
  16. 							String in[]=str.trim().split(" ");
  17. 							int W=Integer.parseInt(in[0]);
  18. 							int n=Integer.parseInt(in[1]);
  19. 							//now making the store table. 
  20. 							int arr_v[]=new int[n+1];
  21. 							int arr_w[]=new int[n+1];
  22. 							arr_v[0]=arr_w[0]=0;
  23. 							for(int i=1;i<=n;i++)
  24. 							{
  25. 								String in2[]=br.readLine().trim().split(" ");//12 3 cost fun
  26. 								arr_w[i]=Integer.parseInt(in2[0]);
  27. 								arr_v[i]=Integer.parseInt(in2[1]);
  28. 							}
  29. 							//store table complete.
  30. 							//now main work
  31. 							int V[][]=new int[n+1][W+1];
  32. 							Arrays.fill(V[0],0);
  33.  
  34. 							for(int i=1;i<=n;i++)
  35. 							{
  36. 								for(int w=0;w<=W;w++)
  37. 								{
  38. 									if((arr_w[i]<w) && (arr_v[i]+V[i-1][w-arr_w[i]])>V[i-1][w])
  39. 										V[i][w]=arr_v[i]+V[i-1][w-arr_w[i]];
  40. 									else
  41. 										V[i][w]=V[i-1][w];
  42. 								}
  43. 							}
  44. 							/////
  45.  
  46. 							int k=W,i=n;
  47. 							int sum=0;
  48. 							while(i>0 && k>0)
  49. 							{
  50. 								if(V[i][k]!=V[i-1][k])
  51. 								{
  52. 									//System.out.print(arr_w[i]+"  "+arr_v[i]+"\n");
  53. 									sum+=arr_w[i];
  54. 									i--;
  55. 									k-=arr_w[i];
  56. 								}
  57. 								else
  58. 									i--;
  59. 							}
  60. 							/////
  61. 							System.out.println(sum+" "+V[n][W]);
  62. 							String blank=br.readLine();
  63. 						}
  64. 						//pw.flush();
  65. 					}
  66. 				}
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
50 10
12 3
15 8
16 9
16 6
10 2
21 9
18 4
12 4
17 8
18 9 

50 10
13 8
19 10
16 8
12 9
10 2
12 8
13 5
15 5
11 7
16 2

0 0
stdout
copy 
49 26
36 32
https://ideone.com/1DbuAF
language:
Java (HotSpot 12)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!