Збирка задачи

SkyDriver

Would like my bananna ?
Член од
31 јули 2008
Мислења
2.140
Поени од реакции
221
Еве им решение за сите три задачи за оние кои пробале да ги решат задачите и не успеале во тоа:

(значи сите 3 решенија се во една задача)...

Код:
#include <iostream>
#include <sstream>

using namespace std;

string IntToString ( int broj )
{
  ostringstream conv;

  conv << broj;

  return conv.str();
}

class Matrici
{
public:
	
	int prvaZadacha(int matrica[8][8])
	{
		int zbirKol[8];
		int zbirRed[8];
		int br = 0;
		int vkupenZbir = 0;

		for(int i = 0; i < 8; i++)
		{
			for(int j=0; j<8; j++)
			{
				br+=matrica[j][i];
			}
			zbirRed[i] = br;
			br = 0;
		}

		br = 0;

		for(int i = 0; i < 8; i++)
		{
			for(int j=0; j<8; j++)
			{
				vkupenZbir += matrica[i][j];
				br+=matrica[i][j];
			}
			zbirKol[i] = br;
			br = 0;
		}

		cout << "Zbirovite na kolonite iznesuvaat: ";

		for(int i = 0; i < 8; i++)
		{
			cout << zbirRed[i] << " ";
		}

		cout << endl;

		cout << "Zbirovite na redovite iznesuvaat: ";

		for(int i = 0; i < 8; i++)
		{
			cout << zbirKol[i] << " ";
		}

		cout << endl;

		cout << "Vkupniot zbir na zbirovite na kolonite i zbirovite na redovite iznesuva: " << vkupenZbir * 2 << endl;
		return 0;
	}

	string vtoraZadacha(int matrica[6][6])
	{
		string mojaMatrica[6][6];
    
		for(int i = 0; i < 6; i++)
		{
			for(int j = 0; j < 6; j++)
			{
				if(matrica[i][j] == 0)
				{
					mojaMatrica[i][j] = "#";
                    } else {
						if(matrica[i][j] % 2 == 0){
							mojaMatrica[i][j] = "*";
						} else {
							mojaMatrica[i][j] = IntToString(matrica[i][j]);
						}
				}
			}
		}

		for(int i = 0; i < 6; i++)
		{
			for(int j = 0; j < 6; j++){
				cout << mojaMatrica[i][j] << " ";
			}
			cout << endl;
		}
		return "";
	}

	string tretaZadacha(string matrica[5][5])
	{
		for(int i = 0; i < 5; i ++)
		{
			for(int j = 0; j < 5; j++)
			{
				string zbor = matrica[i][j];
				string novZbor = "";
				
				for(int x = 0; x < zbor.length(); x++)
				{
					if(!(zbor.at(x) == 'a' || zbor.at(x) == 'e' || zbor.at(x) == 'i' || zbor.at(x) == 'o' || zbor.at(x) == 'u'))
					{
						novZbor+=zbor.at(x);
					}
				}
				matrica[i][j] = novZbor;
			}
		}

		for(int i = 0; i < 5; i++)
		{
			for(int j = 0; j < 5; j++)
			{
				cout << matrica[i][j] << " ";
			}
			cout << endl;
		}

		return "";
	}
};

int main()
{
	Matrici solution = Matrici();

	int prvaMatrica[8][8] = { 1, 4, 6, 3, 8, 0, 8, 5,
				           4, 6, 5, 9, 0, 2, 4, 1,
					   6, 1, 8, 4, 0, 3, 0, 5,
					   9, 3, 2, 2, 1, 5, 7, 9,
					   3, 5, 5, 1, 0, 8, 6, 3,
					   5, 1, 2, 0, 5, 7, 3, 4,
					   7, 3, 9, 6, 4, 0, 2, 1,
					   3, 4, 2, 1, 0, 6, 4, 8 };

	int vtoraMatrica[6][6] = { 4, 5, 6, 1, 2, 1,
				            5, 0, 2, 8, 7, 3,
					    0, 3, 0, 6, 2, 1,
					    6, 5, 4, 0, 8, 5,
					    7, 0, 0, 4, 3, 9,
					    9, 0, 1, 3, 0, 7 };

	string tretaMatrica[5][5] = { "korito", "vazna", "tetratka", "salama", "krusha",
		                               "monitor", "planeta", "mitrolez", "kajgana", "tendzere",
				               "krastavica", "kompjuter", "televizor", "bombona", "tefter",
					       "zvuchnik", "saraund", "zgrada", "lastovica", "kutija" };
	
	solution.prvaZadacha(prvaMatrica);
	cout << endl;
	solution.vtoraZadacha(vtoraMatrica);
	cout << endl;
	solution.tretaZadacha(tretaMatrica);

	cin.get();
}
 
Член од
11 септември 2008
Мислења
106
Поени од реакции
89
Gi resiv i jas prvite dve samo sto gi prati samo ne bev vo moznost da gi pratam.Tretata mi bese malku zbunuvacka i ne ja doresiv no ke ja resam i taa koga ke imam vreme.Taka eve gi prvite dve:
//PRVA ZADACA//
#include<stdio.h>
int main()
{
int mat[8][8],i,j,m,suma=0,sr1=0;
int sr[3];
int sk[3];
for(i=0;i<8;i++)
for(j=0;j<8;j++)
{
printf("mat[%d][%d]= ",i,j);
scanf("%d",&mat[j]);
}

for(i=0;i<8;i++)
{ printf("\n");
for(j=0;j<8;j++)
printf("%d\t",mat[j]);
}
printf("\n\n");
for(i=0;i<8;i++)
{sr=0;
for(j=0;j<8;j++)
{
suma=suma+mat[j];
sr=sr+mat[j];


}
}
for(j=0;j<8;j++)
{sk[j]=0;
for(i=0;i<8;i++)
{
sk[j]=sk[j]+mat[j];


}
}

printf("%d,%d,%d,%d,%d,%d,%d\t",suma,sr[0],sr[1],sr[2],sk[0],sk[1],sk[2]);

scanf("%d",&m);
return 0;
}
//VTORA ZADACA//
#include<stdio.h>
int main()
{
int i,j,c;
int mat[3][3];
for(i=0;i<=3;i++)
for(j=0;j<=3;j++)
{
printf("mat[%d][%d]= ",i,j);
scanf("%d",&mat[j]);
}

for(i=0;i<=3;i++)
{ printf("\n");
for(j=0;j<=3;j++)
printf("%d\t",mat[j]);
}
printf("\n\n");

for(i=0;i<=3;i++)
for(j=0;j<=3;j++)
{
if(mat[j]%2==0)
{
mat[j]=(char)mat[j];
mat[j]='*';
}
if(mat[j]==0)
{
mat[j]=(char)mat[j];
mat[j]='#';

}
}
for(i=0;i<=3;i++)
{ printf("\n");
for(j=0;j<=3;j++)
printf("%d\t",mat[j]);
}
printf("\n\n");
scanf("%d",&c);
return 0;
}

samo ima eden problem vo vtorata zadaca mesto znaci gi vaga brojot na kodovite na znacite taraba iz zvezda 42 i 35.
ako znae nekoj neka kaze kako moze da gi sredam.Inace siguren sum deka e nesto vo ovoj stil
 

SkyDriver

Would like my bananna ?
Член од
31 јули 2008
Мислења
2.140
Поени од реакции
221
Ајде малце и задачи со динамичко програмирање :)

1. Ден на дрвото
Директорот во едно средно училиште решил да организира превоз за сите N ученици до местото на засадување на дрва, на денот на дрвото.
Тој добил понуда од една туристичка агнеција од која му понудиле два типа на на автобуси – поголем и помал кои имаат по А и Bседишта соодветно. За секој од типовите понудиле цена на изнајмување (За првиот цена X денари, а за вториот Y денари). Директорот може да земе неколку поголеми и неколку помали автобуси за превоз на учениците. Тој сака да ја одбере таа комбинација за која ќе потроши намалку пари.
Ако ги знаете овие информации направете програма која ќе ја утвди најниската цена што ќе треба да ја плати директорот за даден број на ученици.

2. Проблем со ранец
Крадец со ранец во кој можат да се сместат N волуменски единици, влегол во просторија , во која што се чуваат скапоцени предмети. Во просторијата има вкупно M типови на предмети, секој во многу големи количини (повеќе отколку што може да се собере во ранецот). За секој тип на предмет позната е неговата вредност V(k) и неговиот волумен Z(k), k=1,M. Сите големини се целобројни. Крадецот сака да го наполни ранецот со најскапоцена содржина. Потребно е да се одредат предметите кои треба (може) да ги стави во ранецот и нивната вкупна вредност.

Едит:

3. Шипки
Напиши програм кој за „n“ број на шипки (со различни должини) ќе ја најде комбинацијата од шипки чиј збир на дплжините на шипки е еднаков со „m“ или најблиску до него (без да ја надминува „m“ должината) такашто решението треба да биде постигнато со најмал број употребени шипки.
 

deXterche

тадаммм
Член од
12 февруари 2006
Мислења
4.920
Поени од реакции
942
Ајде малце и задачи со динамичко програмирање :)

1. Ден на дрвото
Директорот во едно средно училиште решил да организира превоз за сите N ученици до местото на засадување на дрва, на денот на дрвото.
Тој добил понуда од една туристичка агнеција од која му понудиле два типа на на автобуси – поголем и помал кои имаат по А и Bседишта соодветно. За секој од типовите понудиле цена на изнајмување (За првиот цена X денари, а за вториот Y денари). Директорот може да земе неколку поголеми и неколку помали автобуси за превоз на учениците. Тој сака да ја одбере таа комбинација за која ќе потроши намалку пари.
Ако ги знаете овие информации направете програма која ќе ја утвди најниската цена што ќе треба да ја плати директорот за даден број на ученици.
PHP:
function drvo_den($n, $a, $b, $x, $y){
    $broj_avtobusi1=0;
    $broj_avtobusi2=0;
    $najpovolno1=0;
    $najpovolno2=0;
    
    is_float($n/$a)?$broj_avtobusi1=intval($n/$a)+1:$broj_avtobusi1=intval($n/$a);
    is_float($n/$b)?$broj_avtobusi2=intval($n/$b)+1:$broj_avtobusi2=intval($n/$b);

    $najpovolno1=$broj_avtobusi1;
    $najpovolno2=0;

    for($i=0;$i<=$broj_avtobusi1;$i++){
    for($s=0;$s<=$broj_avtobusi2;$s++){
        if((($i*$a)+($s*$b))>$n){
        if((($najpovolno1*$x)+($najpovolno2*$y))>(($i*$x)+($s*$y))){
            $najpovolno1=$i;
            $najpovolno2=$s;
                    }
        }
    }}
    return     'Golemi ' . $najpovolno1 . ', mali ' . $najpovolno2;
}
За другите друг ден, само не ќе е лошо да дадеше и тест влезови и излези колку да можев да споредам

Иначе по мој тестови
влез: drvo_den(581, 25, 20, 800, 650);
излез: Golemi 21, mali 3
----
влез: drvo_den(191, 19, 17, 200, 180);
излез: Golemi 3, mali 8
----
влез: drvo_den(191, 19, 15, 200, 180);
излез: Golemi 7, mali 4
 

SkyDriver

Would like my bananna ?
Член од
31 јули 2008
Мислења
2.140
Поени од реакции
221
Немав ни јас тест каси за задачите затоа така ги пишав :\

Иначе ти малце си утнал ја работата затоа што во задачата се бара цената (али ништо страшно, едно множење на бројот на автобусите со цената на автобусите и ќе се добие крајната цена).

Е сега вака набрзинка ако моите математики се точни ондак и решението ти е точно, гледано според вратените резултатити од 2рата и 3тата тест каса (првата големи бројки има тешко е за тестирање :)).

Едит:

Еве за втората задача во паскал:

Рекурзивно решение:
Код:
procedure napolni(q:integer; var B:integer;   var C:integer);
   var BB, CC,i : integer;
   begin
                 B:=0;
                 C:=0;
                 if q>0 then begin
                             for i:=1 to M do
                                         if Z[i]<=q then begin
                                                     napolni(q-Z[i],BB,CC);
                                                     if BB+V[i]>B then begin
                                                                 B:=BB+V[i];
                                                                 C:=i;
                                                     end;
                                         end;
                 end;
   end.
Решение со динамичко програмирање:
Код:
Var
                 B, C:array[0..1000] of longint;
                 V, Z:array[1..10] of integer;
                 N, M, q, i : integer;
   begin
                 readln(N,M);
                 for i:=1 to M do readln(V[i], Z[i]);
                 B[0]:=0; C[0]:=0;
                 for q:=1 to N do begin
                             B[q]:=0; C[q]:=0;
                             for i:=1 to M do
                                         if Z[i]<=q then
                                                     if B[q-Z[i]]+V[i]>B[q] then begin
                                                     B[q]:=B[q-Z[i]]+V[i];
                                                                 C[q]:=i;
                                                     end;
   end;
   writeln('Optimalna vrednost na sodrzinata na   ranecot e', B[N]);
   writeln('Izbranite predmeti se:'); {se   ispisuvaat nanazad, sto ne e bitno}
   q:=N;
   while c[q]>0 do begin
                 writeln(c[q]);
                             q:=q-z[c[q]];
   end;
   end.
 
Член од
6 јуни 2009
Мислења
3.094
Поени од реакции
445
Ајде малце и задачи со динамичко програмирање :)

1. Ден на дрвото
Директорот во едно средно училиште решил да организира превоз за сите N ученици до местото на засадување на дрва, на денот на дрвото.
Тој добил понуда од една туристичка агнеција од која му понудиле два типа на на автобуси – поголем и помал кои имаат по А и Bседишта соодветно. За секој од типовите понудиле цена на изнајмување (За првиот цена X денари, а за вториот Y денари). Директорот може да земе неколку поголеми и неколку помали автобуси за превоз на учениците. Тој сака да ја одбере таа комбинација за која ќе потроши намалку пари.
Ако ги знаете овие информации направете програма која ќе ја утвди најниската цена што ќе треба да ја плати директорот за даден број на ученици.
За оваа не треба динамичко. Пресметуваш за секој автобус колку чини едно седиште (цена/седишта).
Од најефтиниот автобус по седишта земаш се додека не се приближиш или изедначиш до бројот на ученици.
Пример ако поевтиниот автобус по седиште е со 25 седишта, а има 510 ученици, земаш 20 автобуси * 25 седишта = 500 седишта (се добива со целобројно делење, 510 div 25 во паскал, во C само 510/25), остануваат 10 (пресметуваш остаток 510%25).

Ако остаток > 0
Проверуваш дали бројот на седишта на поевтиниот автобус (цел, не по седиште) е поголем или еднаков со остатокот (10 седишта). Ако е го додаваш тој, ако не додаваш од останатиот.

На крајот би добил N автобуси од едниот, и 0 или 1 од другиот.
 

deXterche

тадаммм
Член од
12 февруари 2006
Мислења
4.920
Поени од реакции
942
За оваа не треба динамичко. Пресметуваш за секој автобус колку чини едно седиште (цена/седишта).
Од најефтиниот автобус по седишта земаш се додека не се приближиш или изедначиш до бројот на ученици.
Пример ако поевтиниот автобус по седиште е со 25 седишта, а има 510 ученици, земаш 20 автобуси * 25 седишта = 500 седишта (се добива со целобројно делење, 510 div 25 во паскал, во C само 510/25), остануваат 10 (пресметуваш остаток 510%25).

Ако остаток > 0
Проверуваш дали бројот на седишта на поевтиниот автобус (цел, не по седиште) е поголем или еднаков со остатокот (10 седишта). Ако е го додаваш тој, ако не додаваш од останатиот.

На крајот би добил N автобуси од едниот, и 0 или 1 од другиот.
Ај претвори го ова во код, нема да ти излезе точно, ја пробав оваа опција уште одма
 
Член од
6 јуни 2009
Мислења
3.094
Поени од реакции
445
Ај претвори го ова во код, нема да ти излезе точно, ја пробав оваа опција уште одма
Арно велиш, грешка бев. Ама мислев преав и ја решив задачава со динамичко.

Код:
#include <stdio.h>
#include <stdlib.h>

int najdiMax(int * niza, int len)
{
	int a = niza[0], i;
	for (i=1; i<len; i++)
	{
		if (niza[i]>a)
			a = niza[i];
	}
	return a;
}

void presmetaj(int N, int * V, int * Z, int len)
{
	int asd = N;
	int optVred[1001], optIndex[1001],  vol[1001],  i, q, temp;
	int rez[15];
	optVred[0] = 0; optIndex[0] = -1; vol[0] = 0;
	N+=najdiMax(Z, len)-1;
	for (q=1; q<=N; q++)
	{
		optVred[q] = 1<<30; optIndex[q] = -1; vol[q]=0;
		for (i=0; i<len; i++)
		{
			if (Z[i]<=q)
			{
				temp = optVred[q-Z[i]]+V[i];
				if (temp < optVred[q])
				{
					optVred[q] = temp;
					optIndex[q] = i;
					vol[q]= vol[q-Z[i]]+Z[i];
				}
			}
		}
	}
	i=asd;
	while  (vol[i]<asd)
		i++;

	q=i;
	//najdi min od optVred[i] do optVred[N]
	for (; i<=N; i++)
	{
		if (optVred[i]<optVred[q])
			q = i;
	}
	temp = q;
	for (i=0; i<len; i++)
		rez[i] = 0;

	while (optIndex[q]>-1)
	{
		rez[optIndex[q]]++;
		q -= Z[optIndex[q]];
	}

	for (i=0; i<len; i++)
		printf("%d ", rez[i]);

	printf("\nvk cena: %d\n", optVred[temp]);
}

int main()
{
	int ceni[2];
	int sedista[2];
	int deca;
	scanf("%d %d %d %d %d", &deca, sedista, sedista+1, ceni, ceni+1);
	presmetaj(deca, ceni, sedista, 2);
	return 0;
}
влез: бр ученици, А седишта, Б седишта, А цена, Б цена
Излез: Број на А, Број на Б, вкупна цена

влез: 581, 25, 20, 800, 650
излез: 21 3 18750
----
влез: 191, 19, 17, 200, 180
излез: 2 9 2020 - кај решениоето од декстерче иди 3 8 2040
----
влез: 191, 19, 15, 200, 180
излез: 7 4 2120
 

deXterche

тадаммм
Член од
12 февруари 2006
Мислења
4.920
Поени од реакции
942

SkyDriver

Would like my bananna ?
Член од
31 јули 2008
Мислења
2.140
Поени од реакции
221
Арно велиш, грешка бев. Ама мислев преав и ја решив задачава со динамичко.
...
влез: бр ученици, А седишта, Б седишта, А цена, Б цена
Излез: Број на А, Број на Б, вкупна цена

влез: 581, 25, 20, 800, 650
излез: 21 3 18750
----
влез: 191, 19, 17, 200, 180
излез: 2 9 2020 - кај решениоето од декстерче иди 3 8 2040
----
влез: 191, 19, 15, 200, 180
излез: 7 4 2120
Или имаш грешка некоја или оверлоад прави некаде ваквиот код...

skydriver@skydriver-desktop:~/Desktop/untitled folder$ ./a.out
500 20 20 100 100
25 0
vk cena: 2500
skydriver@skydriver-desktop:~/Desktop/untitled folder$ ./a.out
1000 50 43 300 280
1 0
vk cena: -1209587851
skydriver@skydriver-desktop:~/Desktop/untitled folder$
 
Член од
6 јуни 2009
Мислења
3.094
Поени од реакции
445
Или имаш грешка некоја или оверлоад прави некаде ваквиот код...
Грешка немав, туку има оверлаод на низата. Низите ми беа со фиксна големина, па пробиваше во последниот пример. Еве го истиот програм со динамички алоцирани низи со malloc (во Ц++ се прави со new)

Код:
#include <stdio.h>
#include <stdlib.h>

int najdiMax(int * niza, int len)
{
	int a = niza[0], i;
	for (i=1; i<len; i++)
	{
		if (niza[i]>a)
			a = niza[i];
	}
	return a;
}

void presmetaj(int N, int * V, int * Z, int len)
{
	int asd = N;
	int i, q, temp;
	int *optVred, *optIndex, *vol, *rez;
	N+=najdiMax(Z, len)-1;

	//Затоа што не е важен програм не проверувам за NULL поинтери (malloc може да врати NULL)
	optVred = (int*)malloc(sizeof(int)*(N+1));
	optIndex = (int*)malloc(sizeof(int)*(N+1));
	vol = (int*)malloc(sizeof(int)*(N+1));
	rez = (int*)malloc(sizeof(int)*len);

	optVred[0] = 0; optIndex[0] = -1; vol[0] = 0;
	for (q=1; q<=N; q++)
	{
		optVred[q] = 1<<30; optIndex[q] = -1; vol[q]=0;
		for (i=0; i<len; i++)
		{
			if (Z[i]<=q)
			{
				temp = optVred[q-Z[i]]+V[i];
				if (temp < optVred[q])
				{
					optVred[q] = temp;
					optIndex[q] = i;
					vol[q]= vol[q-Z[i]]+Z[i];
				}
			}
		}
	}
	i=asd;
	while  (vol[i]<asd)
		i++;

	q=i;
	//najdi min od optVred[i] do optVred[N]
	for (; i<=N; i++)
	{
		if (optVred[i]<optVred[q])
			q = i;
	}
	temp = q;
	for (i=0; i<len; i++)
		rez[i] = 0;

	while (optIndex[q]>-1)
	{
		rez[optIndex[q]]++;
		q -= Z[optIndex[q]];
	}

	for (i=0; i<len; i++)
		printf("%d ", rez[i]);

	printf("\nvk cena: %d\n", optVred[temp]);

	free(optVred); free(optIndex); free(vol); free(rez);
}

int main()
{
	int ceni[2];
	int sedista[2];
	int deca;
	scanf("%d %d %d %d %d", &deca, sedista, sedista+1, ceni, ceni+1);
	presmetaj(deca, ceni, sedista, 2);
	return 0;
}
 

SkyDriver

Would like my bananna ?
Член од
31 јули 2008
Мислења
2.140
Поени од реакции
221
Грешка немав, туку има оверлаод на низата. Низите ми беа со фиксна големина, па пробиваше во последниот пример. Еве го истиот програм со динамички алоцирани низи со malloc (во Ц++ се прави со new)
Е сега изгледа е точно :)
Само ќе мора да најдеш пооптимално решение зашто со волку loop циклуси (башка и вгнездените и if циклусите) трошиш еден тон временски интервали.

Него како и да е, еве ќе ставиме неколку тест каси за првата задача (според вратените вредности од кодот на bibil), па ако некој успее да напише програм кој ќе дава поточни резултати или пооптимален код нека се пофали :)

skydriver@skydriver-desktop:~/Desktop/untitled folder$ ./a.out
1000 50 47 300 280
5 16
vk cena: 5980
skydriver@skydriver-desktop:~/Desktop/untitled folder$ ./a.out
500 30 47 165 300
17 0
vk cena: 2805
skydriver@skydriver-desktop:~/Desktop/untitled folder$ ./a.out
850 40 40 200 200
22 0
vk cena: 4400
skydriver@skydriver-desktop:~/Desktop/untitled folder$ ./a.out
3000 51 49 500 499
55 4
vk cena: 29496
skydriver@skydriver-desktop:~/Desktop/untitled folder$ ./a.out
3500 50 45 350 325
70 0
vk cena: 24500
skydriver@skydriver-desktop:~/Desktop/untitled folder$ ./a.out
1850 12 10 244 244
150 5
vk cena: 37820
 
Член од
6 јуни 2009
Мислења
3.094
Поени од реакции
445
Е сега изгледа е точно :)
Само ќе мора да најдеш пооптимално решение зашто со волку loop циклуси (башка и вгнездените и if циклусите) трошиш еден тон временски интервали.
Е па така е со динамичко, незнам пооптимално. Алгоритмов би работел и со повеќе од два типа автобуси. Првите два for и if во форовите се нормални за секој алгоритам со ДП. Исто и циклусот while(optIndex[q]>-1) е стандарден за ДП.

Имам два фора кои работат со rez, секој по две поминувања. Првиот ги прави 0 променливите од rez а вториот печати. И останатите два циклуси еден while и еден for (еден по друг) заедно имаат поминувања колку бројот на седишта на поголемиот автобус. Тие одат од почетното N (asd=N; - број на ученици) до зголеменото N ( N+=najdiMax(Z, len)-1; )

Значи подолгиот дел е ДП делот, а останатите циклуси не менуваат многу.

------------------------------------------------------------
2. Проблем со ранец
Крадец со ранец во кој можат да се сместат N волуменски единици, влегол во просторија , во која што се чуваат скапоцени предмети. Во просторијата има вкупно M типови на предмети, секој во многу големи количини (повеќе отколку што може да се собере во ранецот). За секој тип на предмет позната е неговата вредност V(k) и неговиот волумен Z(k), k=1,M. Сите големини се целобројни. Крадецот сака да го наполни ранецот со најскапоцена содржина. Потребно е да се одредат предметите кои треба (може) да ги стави во ранецот и нивната вкупна вредност.
Еве ја и втората задача во Ц
Код:
#include <stdio.h>
#include <stdlib.h>

void popolni(int N, int * Vr, int * Gl, int len)
{
	int i, q, temp;
	int *B, *C, *rez;
	//int B[1000], C[1000], rez[20];
	B = (int*)malloc(sizeof(int)*(N+1));
	C = (int*)malloc(sizeof(int)*(N+1));
	rez = (int*)malloc(sizeof(int)*(len));
	B[0] = 0; C[0] = -1;
	for (q=1; q<=N; q++)
	{
		B[q] = 0; C[q] = -1;
		for (i=0; i<len; i++)
		{
			if (Gl[i]<=q)
			{
				temp = B[q-Gl[i]] + Vr[i];
				if (temp > B[q])
				{
					B[q] = temp;
					C[q] = i;
				}
			}
		}
	}
	for (i=0; i<len; i++)
		rez[i] = 0;

	q = N;
	while (C[q]>-1)
	{
		rez[C[q]]++;
		q -= Gl[C[q]];
	}

	for (i=0; i<len; i++)
	{
		if (i==(len-1))
			printf("%d elementi od tip %d\n", rez[i], i);
		else
			printf("%d elementi od tip %d, ", rez[i], i);
	}

	free(B); free(C); free(rez);
		
}

int main()
{
	int i, len, kapacitet,  golemini[20], vrednosti[20];
	printf("Vnesi kapacitet na ranecot, broj na tip na elementi, pa volumen i vrednost za sekoj element:\n");
	scanf("%d %d", &kapacitet, &len);
	for (i=0; i<len; i++)
	{
		scanf("%d %d", golemini+i, vrednosti+i);
	}
	popolni(kapacitet, vrednosti, golemini, len);
	return 0;
}
 

Kajgana Shop

На врв Bottom