Funkcja znajdująca liczby do utworzenia szukanej wartości - problem.
Ostatnio zmodyfikowano 2013-06-11 11:51
corthell Temat założony przez niniejszego użytkownika |
Funkcja znajdująca liczby do utworzenia szukanej wartości - problem. » 2013-06-10 23:32:23 Witam.
Piszę program składający się z kilku modułów. Jednym z nich jest funkcja, która po odczytaniu wartości podanej przez użytkownika zacznie analizować tablicę w której będą już podane jakieś wartości i po ich zsumowaniu wyświetli, które jej elementy tworzą wartość równą podanej przez użytkownika.
żeby to lepiej zobrazować podam przykład:
Jest tablica pudelko_zapalek[]. Zawiera liczby (zapałki) np. 3,18,23,55,12,6,12,17,22,2,8 (ogólnie to mogą być dowolne wartości, także wprowadzane przez użytkownika ale wróćmy do przykładu...)
Teraz np. potrzebuje 37 zapałek... I tu zaczyna się właśnie mój problem ponieważ nie mam pojęcia jak skonstruować taki algorytm, który wyszuka te liczby i je doda tworząc szukaną wartość (jeśli nie będzie możliwości to wyświetli stosowną informacje).
Nie proszę o gotowy kod tylko o jakieś nakierowanie (dodam, że bardzo początkujący ze mnie programista) jednak myślę, że można to zrobić stosując podstawowe instrukcje i wyrażenia języka C++ (tu chodzi raczej o problem natury logicznej :)
Pozdrawiam i proszę o pomoc. |
|
Mitu |
» 2013-06-11 10:27:29 Jeżeli dobrze rozumiem o co Ci chodzi, to masz tutaj problem plecakowy. Rozwiązanie na szybko, bruteforcem po wszystkich możliwych rozwiązaniach: #include <iostream>
int sum( int mask[] ) { int suma = 0; for( int i = 0; i <= 11; i++ ) suma += mask[ i ]; return suma; } void inc( int mask[] ) { for( int i = 0; i < 11; i++ ) { if( mask[ i ] == 0 ) { mask[ i ] = 1; break; } else mask[ i ] = 0; } }
int licz( int dane[], int mask[] ) { int val = 0; for( int i = 0; i < 11; i++ ) { val +=( dane[ i ] * mask[ i ] ); } return val; }
int main() { int dane[] = { 3, 18, 23, 55, 12, 6, 12, 17, 22, 2, 8 }; int mask[ 11 ] = { 0 }; int opt[ 11 ] = { 0 }; int val, best = 0, szuk = 37; do { val = licz( dane, mask ); if( val > best && val <= szuk ) { for( int i = 0; i < 11; i++ ) opt[ i ] = mask[ i ]; best = val; } inc( mask ); } while( sum( mask ) < 11 ); for( int i = 0; i < 11; i++ ) { if( opt[ i ] == 1 ) std::cout << dane[ i ] << " "; } }
Śpieszę się, więc nie miałem okazji wszystkiego sprawdzić. |
|
corthell Temat założony przez niniejszego użytkownika |
» 2013-06-11 11:51:08 Boszz człowieku jak ty to wymyśliłeś? oO Bardziej skomplikowanego rozwiązania chyba nie mogłem sobie wyobrazić :-) Ehh no nic jako "zaawansowany" początkujący zabieram się za analizę... :) Zobaczymy co z tego będzie. Dzięki za " nakierowanie" ;-P
Pozdrawiam. |
|
« 1 » |