fork(1) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. int MAX=20000;
  5.  
  6. //jakos dziala ale nie zwraca optimum z ilus tam przypadkow
  7. /*int szukaj_min(int N, int tab[], int znak_startu)
  8. {
  9.     tab[0]*=znak_startu;
  10.     int min=tab[0];                     //zawiera kolejne wart_predk
  11.     for(int i=0;i<N-1;i++)              //szuka minimum
  12.         {
  13.         if(abs(min-tab[i+1]) >= abs(min+tab[i+1]))
  14.             tab[i+1]*=1;
  15.             else tab[i+1]*=-1;
  16.         min=min+tab[i+1];                  //policz akt predkosc
  17.         }
  18.     return abs(min);
  19. }
  20. */
  21.  
  22. void wyp_tab(int **tab, int w, int k)
  23. {
  24.     for (int i=0;i<w;i++)
  25.         {
  26.         for (int j=0;j<k;j++)
  27.             {tab[i][j]=MAX;}
  28.         }
  29. }
  30. /*void wys_tab(int **tab, int w, int k)
  31. {
  32.     for (int i=0;i<w;i++)
  33.     {
  34.         for (int j=0;j<k;j++)
  35.             cout<<tab[i][j]<<"    ";
  36.         cout<<endl;
  37.     }
  38. }
  39. */
  40.  
  41. int knapsack_mod(int N, int *W, int p)
  42. {
  43.     int min_lokal=MAX;
  44.     int **V=new int*[N];
  45.     for(int i=0; i<N; i++)
  46.         V[i] = new int[p];
  47.     wyp_tab(V,N,p);
  48.     V[0][W[0]]=W[0];
  49.     for (int i=0; i<N-1; i++)
  50.         {
  51.         for (int w=0; w<p; w++)
  52.             {
  53.             if(V[i][w]!=MAX)
  54.                 {
  55.                 int wart_1=V[i][w]+W[i+1];
  56.                 if(V[i][w]+W[i]<=p)
  57.                     V[i+1][wart_1]=wart_1;
  58.                 int wart_2=abs(V[i][w]-W[i+1]);
  59.                 V[i+1][wart_2]=wart_2;
  60.                 }
  61.             }
  62.         }
  63.     for (int i=0; i<p; i++)
  64.         {
  65.         if(V[N-1][i]<min_lokal)
  66.             min_lokal=V[N-1][i];
  67.         }
  68.     for(int i=0; i<N; i++)
  69.         {delete [] V[i];}
  70.     delete [] V;
  71.     return min_lokal;
  72. }
  73.  
  74. int main()
  75. {
  76.     int t=0; //ilosc testów
  77.     int N=0; //ilosc pomiarow
  78.     cin>>t;
  79.     for (int j=0; j<t; j++)
  80.         {
  81.         int *tab, plecak;
  82.         int min_w=MAX;
  83.         int max_w=0, max_ww=0;
  84.         cin>>N;
  85.         tab= new int[N];
  86.         for(int k=0;k<N;k++)                //zwroci max przy okazji
  87.             {cin>>tab[k]; max_w+=tab[k];}
  88.         sort(tab, tab+N, greater <int>() );
  89.         max_ww=max_w;
  90.         if (max_w%2!=0)
  91.             {max_ww=max_w+1;}
  92.         plecak=max(max_ww,tab[0]);
  93.         min_w=knapsack_mod(N,tab,plecak);
  94.         cout<<endl<<min_w<<" "<<max_w<<endl;
  95.         delete [] tab;
  96.         }
  97.     //system("pause");
  98.     return 0;
  99. }
Success #stdin #stdout 0.01s 5404KB
comments (?)
stdin
copy 
3
4
10
3
5
4
5
4
11
5
5
5
5
17
15
6
18
10
stdout
copy 
2 22

0 30

0 66
https://ideone.com/LOQ2ZB
problem SPEEDM, based on SPOJ submission 29314978 (C++ 4.3.2), 2022-03-24 19:27:02
language:
C++ 4.3.2 (gcc-4.3.2)
created:
2 years ago
visibility:
secret

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!