#1886
Rucsac1
Într-un magazin sunt n
obiecte; pentru fiecare se cunoaște greutatea G
și valoarea V
. Un hoț intră în magazin având un rucsac ce poate transporta o greutate maximă GMax
. El va fura anumite obiecte, astfel încât suma greutăților obiectelor furate să nu depășească GMax
.
Să se stabilească câștigul maxim pe care îl poate obține hoțul. Câștigul este egal cu suma valorilor obiectelor furate.
Problema | Rucsac1 | Operații I/O | tastatură/ecran |
---|---|---|---|
Limita timp | 0.1 secunde | Limita memorie |
Total: 64 MB
/
Stivă 8 MB
|
Id soluție | #6198934 | Utilizator | |
Fișier | rucsac1.cpp | Dimensiune | 745 B |
Data încărcării | 17 Octombrie 2017, 16:14 | Scor / rezultat | Eroare de compilare |
rucsac1.cpp:1:21: warning: extra tokens at end of #include directive [enabled by default] #include <iostream> #define NMAX 1050 #include <algorithm> using namespace std; int n; int gmax,cmax,gc,cc; int st[NMAX]; struct ob { int o; int g,c; }a[NMAX*NMAX]; void citire(int i) { if(i>1) citire(i-1); cin>>a[i].g>>a[i].c; } void bkt(int k) { int i; for (i=0;i<=1;i++) { st[k]=i; gc+=a[k].g*st[k]; cc+=a[k].c*st[k]; if(gc<=gmax) { if(k==n) { if(cc>cmax) cmax=cc; } else bkt(k+1); } gc-=a[k].g*st[k]; cc-=a[k].c*st[k]; } } int comp(ob a,ob b) { return a.g>b.g; } int main() { cin>>n>>gmax; citire(n); sort(a+1,a+n+1,comp); int s=0; for(int i=1;i<=n-71&&s<=gmax;i++) { if(s+a[i].g==gmax) {cmax+=a[i].c;s+=a[i].g;} else if(s+a[i].g<gmax) { s+=a[i].g; cmax+=a[i].c; } } cc=cmax; gc=s; if(n-70<=0) bkt(1); else bkt(n-70); cout<<cmax; return 0; } ^ rucsac1.cpp:1:266: warning: invalid suffix on literal; C++11 requires a space between literal and identifier [-Wliteral-suffix] #include <iostream> #define NMAX 1050 #include <algorithm> using namespace std; int n; int gmax,cmax,gc,cc; int st[NMAX]; struct ob { int o; int g,c; }a[NMAX*NMAX]; void citire(int i) { if(i>1) citire(i-1); cin>>a[i].g>>a[i].c; } void bkt(int k) { int i; for (i=0;i<=1;i++) { st[k]=i; gc+=a[k].g*st[k]; cc+=a[k].c*st[k]; if(gc<=gmax) { if(k==n) { if(cc>cmax) cmax=cc; } else bkt(k+1); } gc-=a[k].g*st[k]; cc-=a[k].c*st[k]; } } int comp(ob a,ob b) { return a.g>b.g; } int main() { cin>>n>>gmax; citire(n); sort(a+1,a+n+1,comp); int s=0; for(int i=1;i<=n-71&&s<=gmax;i++) { if(s+a[i].g==gmax) {cmax+=a[i].c;s+=a[i].g;} else if(s+a[i].g<gmax) { s+=a[i].g; cmax+=a[i].c; } } cc=cmax; gc=s; if(n-70<=0) bkt(1); else bkt(n-70); cout<<cmax; return 0; } ^ /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 0 has invalid symbol index 11 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 1 has invalid symbol index 12 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 2 has invalid symbol index 2 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 3 has invalid symbol index 2 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 4 has invalid symbol index 11 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 5 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 6 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 7 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 8 has invalid symbol index 12 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 9 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 10 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 11 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 12 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 13 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 14 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 15 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 16 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 17 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 18 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 19 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 20 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_info): relocation 21 has invalid symbol index 22 /usr/bin/ld: /usr/lib/debug/usr/lib/i386-linux-gnu/crt1.o(.debug_line): relocation 0 has invalid symbol index 2 /usr/lib/gcc/i686-linux-gnu/4.8/../../../i386-linux-gnu/crt1.o: In function \`_start': (.text+0x18): undefined reference to \`main' collect2: error: ld returned 1 exit status
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema Rucsac1 face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.