fork(1) download
copy 
  1.  
  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. 							//finding the track
  46. 							//int k=W,i=n;
  47. 							//int sum=0;
  48. 							//for(int y=0;y<=W;y++)
  49. 								//System.out.print(" "+V[n][y]+" ");
  50. 							//System.out.println();
  51. 							/////topcoder support
  52. 							int y=0;
  53. 							for(y=W;y>=0;y--)
  54. 							{
  55. 								if(V[n][y]!=V[n][y-1])
  56. 									break;
  57.  
  58. 							}
  59. 							y--;
  60. 							/////
  61. 							pw.println(y+" "+V[n][W]);
  62. 							String blank=br.readLine();
  63. 						}
  64. 						pw.flush();
  65. 					}
  66. 				}
Success #stdin #stdout 0.08s 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
48 32
https://ideone.com/xsywq1
language:
Java (HotSpot 12)
created:
10 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!