Cerință:
Cu ajutorul unui rucsac de greutate maximă admisibilă GG trebuie să se transporte
o serie de obiecte din n disponibile, având greutăţile G1, G2, …, Gn, aceste obiecte fiind de
utilităţile C1, C2, …, Cn. Dacă pentru orice obiect i putem să luăm doar o parte
xi∈[0,1] din el, atunci spunem că avem problema continuă a rucsacului.
Indicații de rezolvare:
În problema continuă a rucsacului, prin raportarea utilităţilor la greutăţi obţinem utilităţile pe unitate de greutate, astfel încât va trebui să ordonăm obiectele în funcţie de aceste raporturi şi să le încărcăm, pe cât posibil, în întregime în rucsac, până când acesta se umple. Astfel, reprezentând soluţia în vectorul x, vom pune la început x[i]:=1, până când greutatea rămasă disponibilă, notată GGr, nu mai permite punerea unui obiect în întregime. Atunci, vom face x[i]:=GGr/G[i], ultimul obiect fiind “tăiat”.
Implementare:
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Rucsac { class Program { static void Main(string[] args) { double VR; double VC; double aux; double aux2; double alfa; int n; double[] v = new double[100]; double[] p = new double[100]; double[] ordine = new double[100]; double[] procent = new double[100]; int i, j; double PT; Console.WriteLine("Problema continua a rucsacului (obiectele pot fi taiate)"); Console.WriteLine("Dati Volumul Rucsacului"); VR = Convert.ToInt32(Console.ReadLine()); Console.WriteLine("Dati numarul de obiecte"); n= Convert.ToInt32(Console.ReadLine()); for (i = 1; i <= n; i++) { Console.WriteLine("Obiectul al " + i + "-lea:"); Console.Write(" -volum: "); v[i] = Convert.ToDouble(Console.ReadLine()); Console.Write(" -profit: "); p[i] = Convert.ToDouble(Console.ReadLine()); } for (i = 1; i <= n; i++) { ordine[i] = i; } for (i = 1; i <= n - 1; i++) for (j=i+1; j<=n; j++) { if (p[j] / v[j] > p[i] / v[i]) { aux=p[i]; p[i]=p[j]; p[j]=aux; aux=v[i]; v[i]=v[j]; v[j]=aux; aux2 = ordine[i]; ordine[i] = ordine[j]; ordine[j] = aux2; } } PT = 0; VC = VR; for (i = 1; i <= n; i++) { if (v[i] <= VC) { VC=VC-v[i]; PT=PT+p[i]; procent[i]=100; } else if (VC > 0) { alfa = VC / v[i]; VC = 0; procent[i] = alfa * 100; PT = PT + alfa * p[i]; } else { procent[i]=0; } } Console.WriteLine("Solutia problemei: "); for (i = 1; i <= n; i++) { Console.WriteLine("Se ia {0:C3}% din obiectul {1}", procent[i], ordine[i]); } Console.WriteLine("profitul maxim obtinut este {0:C3}", PT); Console.ReadLine(); } } }
Module Module1 Dim VR As Double Dim VC As Double Dim PT As Double Dim i, j As Integer Dim n As Integer Dim v(100) As String Dim p(100) As String Dim ordine(100) As String Dim procent(100) As String Dim aux As Double Dim aux2 As Integer Dim alfa As Double Sub Main() Console.WriteLine("Problema continua a rucsacului(obiectele pot fi taiate") Console.WriteLine("Dati volumul rucsacului") VR = Convert.ToDouble(Console.ReadLine()) Console.WriteLine("Dati numarul de obiecte") n = Convert.ToInt32(Console.ReadLine()) For i = 1 To n Console.WriteLine("Obiectul al " & i & "-lea:") Console.Write(" -volum: ") v(i) = Convert.ToDouble(Console.ReadLine()) Console.Write(" -profit: ") p(i) = Convert.ToDouble(Console.ReadLine()) Next i For i = 1 To n ordine(i) = i Next i For i = 1 To n - 1 For j = i + 1 To n If (p(j) / v(j) > p(i) / v(i)) Then aux = p(i) p(i) = p(j) p(j) = aux aux = v(i) v(i) = v(j) v(j) = aux aux2 = ordine(i) ordine(i) = ordine(j) ordine(j) = aux2 End If Next j Next i PT = 0 VC = VR For i = 1 To n If (v(i) <= VC) Then VC = VC - v(i) PT = PT + p(i) procent(i) = 100 ElseIf (VC > 0) Then alfa = VC / v(i) VC = 0 procent(i) = alfa * 100 PT = PT + alfa * p(i) Else procent(i) = 0 End If Next i Console.WriteLine("Solutia problemei: ") For i = 1 To n Console.WriteLine("Se ia {0:C3}% din obiectul {1}", procent(i), ordine(i)) Next i Console.WriteLine("profitul maxim obtinut este {0:C3}", PT) Console.ReadLine() End Sub End Module
// RucsacCPP.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; float VR, VC, PT; int n; float v[100]; float p[100]; int ordine[100]; float procent[100]; int i,j; float aux, alfa; int aux2; int main() { cout<<"Problema continua a rucsacului (obiectele pot fi taiate)"<<endl; cout<<"Dati volumul rucsacului "; cin>>VR; cout<<"Dati numarul de obiecte "; cin>>n; for (i=1; i<=n; i++) { cout<<"Obiectul al "<<i<< "-lea "<<endl; cout<<" - volum "; cin>>v[i]; cout<<" - profit "; cin>>p[i]; } for(i=1;i<=n;i++) ordine[i]=i; for(i=1;i<=n-1;i++) for(j=i+1;j<=n;j++) if (p[j]/v[j]>p[i]/v[i]) { aux=p[i]; p[i]=p[j]; p[j]=aux; aux=v[i]; v[i]=v[j]; v[j]=aux; aux2=ordine[i]; ordine[i]=ordine[j]; ordine[j]=aux2; } PT=0; VC=VR; for (i=1; i<=n; i++) { if (v[i]<=VC) { VC=VC-v[i]; // atunci il punem, deci VC scade cu volumul lui i PT=PT+p[i]; // la profitul total se adauga profitul obiectului i procent[i]=100; // obiectul se ia in intregim, adica 100% } else if (VC>0) { //atunci vedem ce procent (parte) din el trebuie luat alfa=VC/v[i]; // punem acea parte VC=0; // rucsacul se umple procent[i]=alfa*100; // memoram cat am luat din acel obiect PT=PT+alfa*p[i]; // crestem profitul total corespunzator profitului partii luate din obiectul i } else // celelalte obiecte nu se mai pun deloc in rucsac (nici partial) procent[i]=0; } cout<<endl; cout<<"Solutia este: "<<endl; for (i=1; i<=n; i++) cout<<"Se ia "<<procent[i]<< "%din obiectul "<<ordine[i]<<"."<<endl; cout<<"profitul maxim obtinut este "<<PT; system ("Pause"); }
Rezultat:
InfoCad Blog 