1340 - Rucsac - Revision history

Andrada378 at 11:48, 5 January 2024

2024-01-05T11:48:52Z

← Older revision		Revision as of 11:48, 5 January 2024
Line 1:		Line 1:
	~~Cerinta:~~		== Cerința ==
	Î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, sau porțiuni de obiecte, astfel încât suma greutăților obiectelor furate să nu depășească GMax.		Î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, sau porțiuni de 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. Câștigul adus de o fracțiune de obiect este direct proporțional cu greutatea fracțiunii.		Să se stabilească câștigul maxim pe care îl poate obține hoțul. Câștigul este egal cu suma valorilor obiectelor furate. Câștigul adus de o fracțiune de obiect este direct proporțional cu greutatea fracțiunii.
	Date de intrare
			== Date de intrare ==
	Programul citește de la tastatură numerele naturale n GMax, iar apoi n perechi de valori naturale G V, reprezentând greutatea, respectiv valoarea fiecărui obiect.		Programul citește de la tastatură numerele naturale n GMax, iar apoi n perechi de valori naturale G V, reprezentând greutatea, respectiv valoarea fiecărui obiect.
	Date de ~~iesire~~
			== Date de ieșire ==
	Programul va afișa pe ecran numărul C, reprezentând câștigul maxim pe care îl poate obține hoțul.		Programul va afișa pe ecran numărul C, reprezentând câștigul maxim pe care îl poate obține hoțul.

	Rezolvare<syntaxhighlight lang="python">		== Restricții și precizări ==
	def ~~maximized_profit~~(n, GMax, obiecte):
	dp = [0] * (GMax + 1)		* 1 ≤ n ≤ 1000;
			* 1 ≤ GMax, G, V ≤ 10000;
			* rezultatul va fi punctat dacă diferența dintre cel afișat de program și cel corect este mai mică decât 0.01.

			== Exemplu: ==
			'''Intrare'''

			4 30

			10 60

			5 50

			12 60

			20 140

			'''Ieșire'''

			220

			== Explicație ==
			Hoțul va lua obiectele 2 și 4 în întregime și jumătate din obiectul 1, obținând un câștig de 220.

			== Rezolvare ==
			<syntaxhighlight lang="python">
			def validare_date(n, GMax, obiecte):
			if not (1 <= n <= 1000):
			raise ValueError("n trebuie să fie între 1 și 1000")

			if not (1 <= GMax <= 10000):
			raise ValueError("GMax trebuie să fie între 1 și 10000")

			for greutate, valoare in obiecte:
			if not (1 <= greutate <= 10000 and 1 <= valoare <= 10000):
			raise ValueError("Greutatea și valoarea fiecărui obiect trebuie să fie între 1 și 10000")

			def castig_maxim(n, GMax, obiecte):
			obiecte.sort(key=lambda x: x[1] / x[0], reverse=True) # Sortează obiectele după raportul valoare/greutate în ordine descrescătoare

	~~for i in range(1, n + 1):~~		castig_total = 0
	~~for j in range(GMax,~~ 0~~, -1):~~		greutate_actuala = 0
	~~if obiecte[i - 1][0] <~~= j:
	~~dp[j] = max(dp[j], dp[j - obiecte[i - 1][0]] + obiecte[i - 1][1] * (obiecte[i - 1][0] / obiecte[i - 1][~~0~~]))~~

	~~return dp[~~GMax]		for obiect in obiecte:
			greutate, valoare = obiect
			if greutate_actuala + greutate <= GMax:
			castig_total += valoare
			greutate_actuala += greutate
			else:
			fractiune = (GMax - greutate_actuala) / greutate # Calculăm cât din obiect putem lua pentru a umple rucsacul
			castig_total += fractiune * valoare
			break

	~~# Citirea datelor de la tastatură~~		return castig_total
	~~n = int(input("Introdu numărul de obiecte: "))~~
	~~GMax = int(input("Introdu greutatea maximă ce poate fi transportată: "))~~

	~~obiecte = []~~		# Citirea datelor de intrare
	~~print("Introdu greutatea și valoarea pentru fiecare obiect:")~~		n, GMax = map(int, input().split())
	~~for i in range(~~n):		obiecte = [tuple(map(int, input().split())) for _ in range(n)]
	G, V = map(int, input().split())
	obiecte~~.append~~((G, V))

	~~max_profit~~ = ~~maximized_profit~~(n, GMax, obiecte)		# Calcularea și afișarea câștigului maxim
	print(~~max_profit~~)		rezultat = castig_maxim(n, GMax, obiecte)
			print(rezultat)
	</syntaxhighlight>		</syntaxhighlight>

Andrada378 at 13:56, 28 December 2023

2023-12-28T13:56:44Z

← Older revision		Revision as of 13:56, 28 December 2023
Line 8:		Line 8:
	Programul va afișa pe ecran numărul C, reprezentând câștigul maxim pe care îl poate obține hoțul.		Programul va afișa pe ecran numărul C, reprezentând câștigul maxim pe care îl poate obține hoțul.

	Rezolvare		Rezolvare<syntaxhighlight lang="python">
	def maximized_profit(n, GMax, obiecte):		def maximized_profit(n, GMax, obiecte):
	dp = [0] * (GMax + 1)		dp = [0] * (GMax + 1)

	for i in range(1, n + 1):		for i in range(1, n + 1):
	for j in range(GMax, 0, -1):		for j in range(GMax, 0, -1):
	if obiecte[i - 1][0] <= j:		if obiecte[i - 1][0] <= j:
	dp[j] = max(dp[j], dp[j - obiecte[i - 1][0]] + obiecte[i - 1][1] * (obiecte[i - 1][0] / obiecte[i - 1][0]))		dp[j] = max(dp[j], dp[j - obiecte[i - 1][0]] + obiecte[i - 1][1] * (obiecte[i - 1][0] / obiecte[i - 1][0]))

	return dp[GMax]		return dp[GMax]

	# Citirea datelor de la tastatură		# Citirea datelor de la tastatură
	n = int(input("Introdu numărul de obiecte: "))		n = int(input("Introdu numărul de obiecte: "))
	GMax = int(input("Introdu greutatea maximă ce poate fi transportată: "))		GMax = int(input("Introdu greutatea maximă ce poate fi transportată: "))

	obiecte = []		obiecte = []
	print("Introdu greutatea și valoarea pentru fiecare obiect:")		print("Introdu greutatea și valoarea pentru fiecare obiect:")
	for i in range(n):		for i in range(n):
	G, V = map(int, input().split())		G, V = map(int, input().split())
	obiecte.append((G, V))		obiecte.append((G, V))

	max_profit = maximized_profit(n, GMax, obiecte)		max_profit = maximized_profit(n, GMax, obiecte)
	print(max_profit)		print(max_profit)
			</syntaxhighlight>

Andrada378 at 17:09, 13 December 2023

2023-12-13T17:09:56Z

← Older revision		Revision as of 17:09, 13 December 2023
Line 7:		Line 7:
	Date de iesire		Date de iesire
	Programul va afișa pe ecran numărul C, reprezentând câștigul maxim pe care îl poate obține hoțul.		Programul va afișa pe ecran numărul C, reprezentând câștigul maxim pe care îl poate obține hoțul.

	Rezolvare		Rezolvare
			def maximized_profit(n, GMax, obiecte):
	def maximized_profit(n, GMax, obiecte):		dp = [0] * (GMax + 1)
	dp = [0] * (GMax + 1)
			for i in range(1, n + 1):
	for i in range(1, n + 1):		for j in range(GMax, 0, -1):
	for j in range(GMax, 0, -1):		if obiecte[i - 1][0] <= j:
	if obiecte[i - 1][0] <= j:		dp[j] = max(dp[j], dp[j - obiecte[i - 1][0]] + obiecte[i - 1][1] * (obiecte[i - 1][0] / obiecte[i - 1][0]))
	dp[j] = max(dp[j], dp[j - obiecte[i - 1][0]] + obiecte[i - 1][1] * (obiecte[i - 1][0] / obiecte[i - 1][0]))
			return dp[GMax]
	return dp[GMax]
			# Citirea datelor de la tastatură
	# Citirea datelor de la tastatură		n = int(input("Introdu numărul de obiecte: "))
	n = int(input("Introdu numărul de obiecte: "))		GMax = int(input("Introdu greutatea maximă ce poate fi transportată: "))
	GMax = int(input("Introdu greutatea maximă ce poate fi transportată: "))
			obiecte = []
	obiecte = []		print("Introdu greutatea și valoarea pentru fiecare obiect:")
	print("Introdu greutatea și valoarea pentru fiecare obiect:")		for i in range(n):
	for i in range(n):		G, V = map(int, input().split())
	G, V = map(int, input().split())		obiecte.append((G, V))
	obiecte.append((G, V))
			max_profit = maximized_profit(n, GMax, obiecte)
	max_profit = maximized_profit(n, GMax, obiecte)		print(max_profit)
	print(max_profit)

Andrada378: Pagină nouă: Cerinta: Î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, sau porțiuni de 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. Câștigul adus de o fracțiun...

2023-12-13T17:06:56Z

Pagină nouă: Cerinta: Î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, sau porțiuni de 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. Câștigul adus de o fracțiun...

New page

Cerinta:
Î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, sau porțiuni de 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. Câștigul adus de o fracțiune de obiect este direct proporțional cu greutatea fracțiunii.
Date de intrare
Programul citește de la tastatură numerele naturale n GMax, iar apoi n perechi de valori naturale G V, reprezentând greutatea, respectiv valoarea fiecărui obiect.
Date de iesire
Programul va afișa pe ecran numărul C, reprezentând câștigul maxim pe care îl poate obține hoțul.
Rezolvare

def maximized_profit(n, GMax, obiecte):
dp = [0] * (GMax + 1)

for i in range(1, n + 1):
for j in range(GMax, 0, -1):
if obiecte[i - 1][0] <= j:
dp[j] = max(dp[j], dp[j - obiecte[i - 1][0]] + obiecte[i - 1][1] * (obiecte[i - 1][0] / obiecte[i - 1][0]))

return dp[GMax]

# Citirea datelor de la tastatură
n = int(input("Introdu numărul de obiecte: "))
GMax = int(input("Introdu greutatea maximă ce poate fi transportată: "))

obiecte = []
print("Introdu greutatea și valoarea pentru fiecare obiect:")
for i in range(n):
G, V = map(int, input().split())
obiecte.append((G, V))

max_profit = maximized_profit(n, GMax, obiecte)
print(max_profit)