Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

problem plecakowy brute force

Ostatnio zmodyfikowano 2017-06-02 22:54
Autor Wiadomość
mikewazowski
Temat założony przez niniejszego użytkownika
problem plecakowy brute force
» 2017-06-02 21:51:22
Muszę wykonać przegląd wyczerpujący w problemie plecakowym - mam problem z funkcją bruteforce() która zawsze zwraca największą cenę zamiast rozwiązania problemu.
Proszę o wskazówki gdzie popełniam błąd lub o pseudokod który pomoże napisać mi funkcję od nowa (oraz wyrozumiałość, dopiero się uczę)
C/C++
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <time.h>
using namespace std;
int bruteforce( int ceny[], int wagi[], int W, int waga, int cena )
{
    int * A = new int[ W ];
   
    for( int i = 0; i < W; i++ ) {
        int j = W;
        int xwaga = 0;
        int xcena = 0;
        int k;
       
        k = 1;
        for( j = 0; j < W; j++ ) {
            A[ j ] += k;
           
            k = A[ j ] / 2;
            A[ j ] = A[ j ] % 2;
        }
        if( k ) break;
       
        for( k = 0; k < W; k++ ) {
            if( A[ k ] == 1 ) {
                xwaga = xwaga + wagi[ k ];
                xcena = xcena + ceny[ k ];
            }
        }
       
        if( xcena > cena && xwaga <= waga ) {
            cena = xcena;
        }
    }
   
    return cena;
}

int main()
{
   
    int n, W, waga, cena;
   
    cout << endl << "pojemnosc placaka: ";
    cin >> W;
    cout << "ile przedmiotow:";
    cin >> n;
    cout << endl;
   
    int * ceny = new int[ n + 1 ];
    int * wagi = new int[ n + 1 ];
   
    for( int i = 0; i < n; i++ )
    {
        waga =( rand() % 100 ) + 1;
        cena =( rand() % 100 ) + 1;
        ceny[ i ] = cena;
        wagi[ i ] = waga;
        cout << "cena: " << ceny[ i ] << " waga: " << wagi[ i ] << endl;
    }
   
    cout << "----------------" << endl;
    int najcenniejszy = ceny[ 0 ];
   
    for( int i = 0; i < n; i++ )
    {
        if( ceny[ i ] > najcenniejszy )
             najcenniejszy = ceny[ i ];
       
    }
    cout << "NAJCENNIEJSZY: " << najcenniejszy << endl;
    int najciezszy = wagi[ 0 ];
    for( int i = 0; i < n; i++ )
    {
        if( wagi[ i ] > najciezszy )
             najciezszy = wagi[ i ];
       
    }
    cout << "NAJCIEZSZY: " << najciezszy << endl;
    cout << "----------------" << endl;
   
    cout << "brute force: " << bruteforce( ceny, wagi, n, najciezszy, najcenniejszy ) << endl;
   
    return 0;
}
P-161996
czaffik
» 2017-06-02 22:34:06
1. Opisz dokładniej o co chodzi w tym problemie, nie każdy musi wiedzieć;
2. Staraj się sensowniej nazywać zmienne i trzymać schematu, zamiast pojemność oznaczać jako W po prostu oznaczaj jako pojemnosc, unikniesz wątpliwych sytuacji gdzie zmienna W w pętli głównej oznacza pojemność a w funkcji bruteforce ilość, pogubić się można;
P-161998
mikewazowski
Temat założony przez niniejszego użytkownika
» 2017-06-02 22:39:56
1. Opis problemu: mając plecak o objętośći W chcemy włożyć do niego tyle przedmiotów by suma ich wag nie przekroczyła objętości a suma cen była jak najwyższa ; metoda brute force to algorytm sprawdzający wszystkie istniejące rozwiązania i wybierający optymalne
2. co do zmiennych - dziękuję za uwagę, postaram się pisać czytelniej

P-162000
czaffik
» 2017-06-02 22:54:48
1. tj chodzi o to żeby waga przedmiotów była równa maksymalnej wadze jaką można przenieść plecakiem? Sorry za czepianie się ale jeśli czasami nie nazywa się dobrze zmiennych to idzie się łatwo pogubić;
2. według mnie deklaracja funkcji powinna wyglądać tak:
C/C++
int bruteforce( int * ceny, int * wagi, int ilosc, int pojemnosc, int najcenniejszy )
- czyli przesyłasz tablice cen i wag przedmiotów, ilość przedmiotów, pojemność plecaka (lub maksymalną wagę) oraz najcenniejszy przedmiot jeśli do czegoś potrzebny choć nie jestem pewien.
3. Na początek możesz zrobić tak: uporządkować tablicę względem cen, najcenniejsze na początek, potem dodawać przedmioty od początku i sumować wagę i sprawdzać czy waga nie przekracza maksymalnej wagi jaką może unieść plecak, na koniec posumować ceny przedmiotów które są w plecaku.
4. Mała poprawka, zamiast sortować względem ceny lepiej ustalić stosunek ceny do wagi dla każdego przedmiotu i po tym sortować.
P-162002
« 1 »
  Strona 1 z 1