Problem u zadatku Novcani Sistem - Rekurzije

Pitanja i problemi
1

Problem u zadatku Novcani Sistem - Rekurzije

Na primerima 5 i 9 imam TLE. Da li neko moze da mi kaze sta nije u redu sa mojim resenjem (kako da se zadatak resi na neki brzi nacin)? Ovo je moj kod:

#include<iostream>
#include<vector>
using namespace std;
vector<int> resenje;
vector<int> novcanice;
int n;
bool dali(int m){
    if(m==0){
	    cout<<"DA"<<endl;
	    return true;
    }else if(m<0){
	    return false;
    }
    for(int i=0;i<n;i++){
	    if(dali(m-novcanice[i])){
		    resenje[i]++;
		    return true;
	    }
    }
    return false;
}
int main(){
    int m;
    cin>>n>>m;
    novcanice.resize(n);
    for(int i=0;i<n;i++){
	    cin>>novcanice[i];
    }
    resenje.resize(n,0);
    if(dali(m)){
	    for(int i=0;i<n;i++){
		    cout<<resenje[i]<<" ";
	    }	
    }else{
	    cout<<"NE";
    }
    return 0;
}

Link ka zadatku —> https://petlja.org/BubbleBee/r/Problems/-19

2

Postoji jednostavnije rešenje, nisam koristio rekurziju ali mislim da ces se snaći. Kod

U tvom rešenju si bespotrebno oduzimao, mogao si jednostavno da zameniš oduzimanje deljenjem, pri čemu bi nova suma bila ostatak pri deljenju sa trenutnom novčanicom.

1 Like
3

@milosh Tvoj kod prolazi kroz sve test primere, ali ako dam primer sa 2 novcanice (2, 3) i treba da dobijem 9 (to je ocigledno moguce (3, 1 ili 0, 3)) tvoj kod ce da ispise NE zato sto moze da koristi najvise 4 dvojke i ostatak je 1 sto ne moze da dobije i nece isprobati druge mogucnosti.

4

Onda da mozda pre izracunavanja prodjes kroz elemente i proveris da li je suma deljiva sa nekim od njih?

5

@milosh To bi popravilo onaj primer, ali ne bi popravilo primer sa novcanicama (3 i 4) a treba da dobijemo 10, 10 nije deljivo ni sa 3 ni sa 4 i tvoj kod ce opet ispisati NE zato sto ce dobiti da je ostatak pri deljenju 10 sa 3 jedank 1 i 1 ne moze da dobije, ali resenje postoji i to je 2 puta 3 i jedna od 4.

6

Ah izvini, onda mozemo da problem resimo preko DP,
Napravimo niz A[n], postavimo sve elemente na false, sem A[0]. Sada prodjemo kroz sve brojeve, neka je trenutni broj X, sada postavljamo niz A na sledeci nacin: A[i] = A[i] || A[i-X], a i ide X do sume. A[S] nam govori da li je moguce da formiramo tu sumu. Da bismo rekonstruisali resenje, za svako A[i] oznacimo novu vrednost B[i] koja nam govori da je taj broj X ucinio A[i] true.

Kod

1 Like
7

Sada cu da pokusam da napisem kod pa cu da vidim da li radi, ali zvuci dobro.

8

Hvala ti puno, resenje radi za sve test primere (i ove sto sam gore naveo) puno si mi pomogao.

9

Nema na cemu, i izvini mislio sam da moze da se resi bez DP :)))

10

Ja sam mislio da moze sa rekurzijama zato sto je zadatak u odeljku “Rekurzija”.

11

Ustvari i moze.

12

@MilosP Ali nece raditi primer sa novcanicama 2 i 7, a treba da dobijemo 11, to je moguce, 2 puta od 2 i jedna od 7, ali ce tvoj kod da ispise NE, to je bio problem i sa onim drugim idejama, tvoja je skoro ista samo sto ce da isproba i maks-1, ali u ovom slucaju idalje nece da dobije dobro resenje. (Kod ce svakako proci kroz sve test primere, ali samo zato sto su bezveze napisani i nema nijedan primer ovog oblika). Ovo je moj kod sa DP koji radi i za ovakve primere:

Kod 
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int m,n;
    cin>>n>>m;
    vector<int> novcanice(n);
    for(int i=0;i<n;i++){
	    cin>>novcanice[i];
    }
    vector<bool> a(m+1,false);
    vector<int> b(m+1);
    vector<int> resenje(n,0);
    a[0]=true;
    for(int i=0;i<m+1;i++){
	    for(int j=0;j<n;j++){
		    if(i-novcanice[j]>=0){
			    if(a[i-novcanice[j]]){
				    b[i]=j;
				    a[i]=a[i-novcanice[j]];
			    }
		    }
	    }
    }
    if(a[m]){
	    cout<<"DA"<<endl;
	    for(int i=m;i>0;){
		    resenje[b[i]]++;
		    i-=novcanice[b[i]];
	    }
	    for(int i=0;i<n;i++){
		    cout<<resenje[i]<<" ";
	    }
    }else{
	    cout<<"NE";
    }
    return 0;
}
13

Sada sam primetio kod koji si dodao i video da nece lepo da ispise kako treba da se dobije resenje, ali je ipak imao sve tacne test primere i onda sam napravio program koji samo ispisuje DA i dobio sve tacno tako da proveravanje uopste ne gleda da li je lepo ispisano kako da se dobije resenje xD.