Ciągły problem plecakowy
Kod był wyświetlany 2926 razy.
    /*
Name: Ciagly problem plecakowy
Copyright: GPL GNU
Date:25-03-09 18:18
Description: Naszym zadaniem jest nabrac do plecaka przedmiotow tak,
zeby ich wartosc byla jak najwieksza,
jednoczesnie nie przekraczajac granicy jego wytrzymalosci.
Nie trzeba brac calych przedmiotow, mozna brac tez czesci.
*/

#include <iostream>

using namespace std;
int main()
{
int n,i,j,*orginalny,*wynik;
float *waga,*wartosc,*stosunki,maxWartosc=0,limit,*czesc;

cout<<"\n\n\tPodaj ilosc rzeczy: ";
cin>>n;
cout<<"\n\tPodaj limit plecaka: ";
cin>>limit;

waga=new float[n];
wartosc=new float[n];
stosunki=new float[n];
orginalny=new int[n];
wynik=new int[n];
czesc=new float[n];

cout<<endl;

for(i=0;i<n;i++)
{
                cout<<"\n\tPodaj wage rzeczy nr "<<i+1<<": ";
                cin>>waga[i];
                cout<<"\n\tPodaj wartosc rzeczy nr "<<i+1<<": ";
                cin>>wartosc[i];
                stosunki[i]=wartosc[i]/waga[i];
                orginalny[i]=i;
                }

for(i=0;i<n-1;i++)
{
                  for(j=0;j<n-i-1;j++)
                  {
                                      if(stosunki[j]<stosunki[j+1])
                                      {
                                             swap(stosunki[j],stosunki[j+1]);
                                             swap(waga[j],waga[j+1]);
                                             swap(wartosc[j],wartosc[j+1]);
                                             swap(orginalny[j],orginalny[j+1]);
                                             }
                                      }
                  }

for(i=0,j=0;i<n;i++)
{
if(waga[i]>=limit)
{
                  wynik[j]=orginalny[i]+1;
                  czesc[j]=limit/waga[i];
                  limit-=waga[i];
                  j++;
                  maxWartosc+=wartosc[i];
                  break;
                  }
else
{
    limit-=waga[i];
    wynik[j]=orginalny[i]+1;
    czesc[j]=1;
    maxWartosc+=wartosc[i];
    j++;
    }
}

cout<<"\n\n\tWartosc plecaka: "<<maxWartosc<<"\n\n\t";
cout<<"W plecaku znajduja sie nastepujace przedmioty: \n\n\t";
for(i=0;i<j;i++)
{
                if(czesc[i]!=1)
                cout<<czesc[i]<<" czesc przedmiotu nr "<<wynik[i]<<"\n\t";
                else
                cout<<"Przedmiot nr "<<wynik[i]<<"\n\t";
                }

cout<<"\n\t";
system("pause");
return 0;
}
    
Pobierz plik tekstowy
Administrator WJL
PHP&SQL coded by NOVA-IT