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