Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on May 7th, 2012  |  syntax: None  |  size: 1.39 KB  |  hits: 13  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.io.OutputStreamWriter;
  5. import java.io.PrintWriter;
  6. import java.util.Scanner;
  7. import java.util.StringTokenizer;
  8.  
  9.  
  10.  
  11. public class Main {
  12.  
  13.     public static void main(String[] args) throws NumberFormatException, IOException
  14.         {
  15.                 Scanner sc=new Scanner(System.in);
  16.                 int ileTestow=sc.nextInt();
  17.                 String odps="";
  18.                
  19.                 while(ileTestow-->0)
  20.                 {
  21.                         int ileZawodnikow=sc.nextInt();
  22.                         int co =1;
  23.                        
  24.                         int cena[]=new int[ileZawodnikow+1];
  25.                         int umiejetnosc[]=new int[ileZawodnikow+1];
  26.                         while(co<=ileZawodnikow)
  27.                         {
  28.                                
  29.                                 umiejetnosc[co]=sc.nextInt();
  30.                                 cena[co]=sc.nextInt();
  31.                                 co++;
  32.                         }
  33.                         int budzet=sc.nextInt();
  34.                         int [][]odp=new int[ileZawodnikow+1][budzet+1];
  35.                         boolean [][]czyw=new boolean[ileZawodnikow+1][budzet+1];
  36.                         for(int i=1;i<=ileZawodnikow;i++)
  37.                                 for(int j=1;j<=budzet;j++)
  38.                                         if(cena[i] >j)
  39.                                         {
  40.                                                 odp[i][j]=odp[i-1][j];
  41.                                                
  42.                                         }
  43.                                         else
  44.                                         {
  45.                                                 if(odp[i-1][j]>=odp[i-1][j-cena[i]] + umiejetnosc[i])
  46.                                                 {
  47.                                                         odp[i][j]=odp[i-1][j];
  48.                                                        
  49.                                                 }
  50.                                                 else
  51.                                                 {
  52.                                                         odp[i][j]=odp[i-1][j-cena[i]] + umiejetnosc[i];
  53.                                                         czyw[i][j]=true;
  54.                                                 }
  55.                                                        
  56.                                         }
  57.                         odps="";
  58.                         for(int i=ileZawodnikow,j=budzet;i>0;i--)
  59.                         {
  60.                                 if(czyw[i][j])
  61.                                 {
  62.                                         odps=i+" "+odps;
  63.                                         j=j-cena[i];
  64.                                 }
  65.                                
  66.                         }
  67.                         System.out.println(odps);
  68.                        
  69.                 }
  70.                
  71.                
  72.  
  73.         }
  74.  
  75. }
create a new version of this paste RAW Paste Data