Problem plecakowy
Kod był wyświetlany 4487 razy.
    /*
  Name: Problem plecakowy 
  Copyright: GPL GNU
   Date: 26-10-07 13:37
  Description: 
  Dane są przedmioty o wagach: c1, . . . , ck.
Pytanie 1: Czy istnieje taki zestaw przedmiotów, których łączna waga jest równa s.
Pytanie 2: Które przedmioty należy zapakować do plecaka, aby ich łączną waga była
największa, ale nie przekraczała s.
Algorytm: Rozpatrzenie wszystkich podzbiorów zbioru przedmiotów i sprawdzenie,
które z tych podzbiorów spełniają warunki zadania.
E. Kombinacje k-elementowe.
Algorytm: Kombinacje
Dane: k - długość kombinacji, n - liczność zbioru
Wynik: ciag k- elementowych kombinacji w porzadku leksykograficznym.
A[k] - reprezentacja pojedynczej kombinacji. Stan początkowy A = (1, . . . , k)
function kombinacje { p = k
while p ­ 1 { Write (A)
if (A[k] = n) then p = p - 1
else p = k
if (p ­ 1) then { for i = k downto p
A[i] = A[p] + i - p + 1
}
}
}
*/

#include <cstdlib>
#include <iostream>
#include <vector>
#include <cstdio>

#define iter(a) for(int i = 0  ; i< a ; i++) //coby duzo nie pisac robimy skrocony zapis petli for

int compare (const void * a, const void * b)
{
  return ( *(int*)b - *(int*)a ); //funkcja aby posortowac malejaco
}

using namespace std;
int sumaW(vector<int>&);

int main(int argc, char *argv[])
{
    int k,suma;
    suma = 0;
    
    cout<<"Podaj ilosc przedmiotow: ";
    cin>>k;
    
    cout<<"Podaj wagi kolejnych przedmiotow, oddziel spacja: ";
    int * przedmioty = new int[k];
    
    iter(k)
    {
    cin>>przedmioty[i];         
    }
    
    int waga;
    
    cout<<"Podaj wage, jaka chcesz uzyskac: ";
    cin>>waga;
    
     if(waga <= 0)
     {
      cout<<"blad danych...";
      cin.ignore();
      getchar();
      exit(0);        
     }
    
    vector<int> mozliwosc, optymalny; //mozliwosc przechowuje kazda brana pod uwage mozliwosc
                                      //optymalny przechowuje najwieksza mozliwosc mniejsza od szukanej
    
    qsort(przedmioty, k, sizeof(int), compare);
    
     for(int j = k-1 ; j>= 0; j-- )
     {
      
      mozliwosc.clear();
      suma = 0;
     
      for(int i = j; i >= 0; i--)
      {
       if(przedmioty[i] == waga)
       {
        mozliwosc.push_back(przedmioty[i]);                 
       }
       if(przedmioty[i] > waga) continue; 
       
       if(suma + przedmioty[i] > waga)
       continue;
       
       suma += przedmioty[i];
       mozliwosc.push_back(przedmioty[i]);   
      }   
      
       if(suma == waga)
        break;
        
        if(sumaW(optymalny) < sumaW(mozliwosc))
        {
         optymalny.clear();
          
          iter(mozliwosc.size())
           optymalny.push_back(mozliwosc[i]); //kopiowanie wektora                        
        }
     }
     
     if(suma != waga)
     {
      cout<<"Nie ma mozliwosci takiego spakowania elementow "<<endl;
      cout<<"Aby zapakowane elementy mialy najwieksza mase naleze spakowac elementy: ";
       iter(optymalny.size())
        cout<<optymalny[i]<<" ";       
     } else
       {
        cout<<"Istnieje taka  mozliwosc, nalezy spakowac elementy o masach: ";
         iter(mozliwosc.size())
         {
          cout<<mozliwosc[i]<<" ";                        
         }    
       }
    
    cin.ignore();
    getchar();
    return 0;
}


int sumaW(vector<int>& v)
{
 int suma = 0;
 iter(v.size())
 {
  suma+=v[i];   
 }   
 
 return suma;  
}

    
Pobierz plik tekstowy
Administrator WJL
PHP&SQL coded by NOVA-IT