InfoAs Atlas

<- Go back View preview

Problema Rucsac 3

Identification properties

🔒 The following are read-only properties. If you wish to change them, please create a new problem.

Name

Content ID

Hash Note: The hash is stored in the filesystem.

Content properties

Task

Examples

Default code

Summary

Editorial

**Algoritm.** Algoritmul după care funcționează problema rucsacului este următoarea:

Notăm cu `greu(i)` greutatea obiectului `i`, `val(i)` valoarea obiectului `i` și `dp(i, j)` valoarea maximă ce se poate obține selectând o submulțime de obiecte dintre primele `i`, cu greutatea totală mai mică sau egală cu `j`.

Pentru a calcula `dp(i, j)`, avem două posibilități:

* dacă greutatea obiectului `i` este mai mică sau egală decât `j` (pentru că în caz contrar ar depăși greutatea maximă `j`) și valoarea obiectului `i`, adunată cu `dp(i - 1, j - greu(i))` este mai mare decât `dp(i - 1, j)` (adică este mai profitabil să luăm obiectul `i`), atunci `dp(i, j) = val(i) + dp(i - 1, j - greu(i))`;
  * în caz contrar, nu putem face nimic, decât să nu luăm obiectul `i` în considerare: `dp(i, j) = dp(i - 1, j)`.

Răspunsul final se află în `dp(n, gmax)`.

**Optimizare necesară.** Observăm că limita de memorie nu ne permite să avem o matrice cu `1000 * 1000` de elemente. Totodată, vedem că atunci când prelucrăm `dp(i, j)`, depindem doar de linia anterioară `i - 1` și de nicio altă linie anterioară. Din acest motiv, putem reduce matricea la una de `2 * 1000` de elemente, iar în loc de `dp(i, j)`, scriem `dp(i % 2, j)`, și în loc de `dp(i - 1, j)`, scriem `dp(1 - (i % 2), j)`. Făcând acest lucru, economisim o imensă parte din memorie.

Solution

Contributor ID

Author

Tags

Problem set

Chapter ID

Published At

Admin Approved

Difficulty

License

File name	Description	Updated at	Size	Actions
hash.txt	Special file The hash of all the content of a problem. Autogenerated.	10 January 2025 21:26	64 B	View
manifest.json	Special file Metadata for the problem. Autogenerated.	10 January 2025 21:26	856 B	View
0-rucsac-3.in	/ 100	10 January 2025 21:26	28 B	View
0-rucsac-3.ok	/ 100	10 January 2025 21:26	2 B	View
1-rucsac-3.in	/ 100	10 January 2025 21:26	1 KB	View
1-rucsac-3.ok	/ 100	10 January 2025 21:26	4 B	View
2-rucsac-3.in	/ 100	10 January 2025 21:26	4 KB	View
2-rucsac-3.ok	/ 100	10 January 2025 21:26	4 B	View
3-rucsac-3.in	/ 100	10 January 2025 21:26	5 KB	View
3-rucsac-3.ok	/ 100	10 January 2025 21:26	4 B	View
In total: 10 files 12 KB

View files grouped by their test cases.

Index	Input file	Output file	Score	Visibility

Enzo Judge

Offline

Server is offline.

Fernando Judge

Offline

Server is offline.

Main Instance

Offline

Server is offline.

Judge count: 2 Instance count: 1

Online judges will be synchronised with all the files. The previous version(s) of the problem will be overwritten.

Problema Rucsac 3

Identification properties

Content properties

Technical properties

Delete all files