c++ programming part 16

Curs gratuit cu program de internship de programare java- taxa de inscriere 100 lei, Ploiesti
Rel. la 0729 131 325

1307. Note: Using this method, we do not always come to a solution,
1308. even if it exists.
1309. But if we get there, it will definitely be the best one.
1310. Example :
1311. Coin problem.
1312. An amount S is given (for example, $ 100).
1313. There are coins worth: 12 usd, 15 usd, 4 usd (we assume that there are).
1314. Change the amount S using the minimum number of coins.
1315. Obviously, we will sort the string by the coin values: 15, 12, 4.

1316. Change 90 usd with 6 coins of 5 usd and 10 lei. We can not use it the value of 12
usd, we go to the next value, that is 4 usd. We use 2 coins of 4 lei, and 2 lei. We have
not reached a solution, that is, we have not changed
1317. the whole amount. Instead, if we started with the 12 lei, we would have used
coins and there would still be 4 lei (100-96). The last currency of 4 could be used
usd. 1318. Even using the 4 usd currency, the whole amount could be changed.
1319. What is the solution: a technique made up of the two techniques, backtracking
and greedy. It generates all the solutions to the problem, and at each step the best
one is retained
1320. better, in a separate vector, the vector SOLUTION. Generate solution 1.
1321. Generate solution 2. Is it better than previous solution? If yes, it is
1322. retains the same until the last solution is tested.
1323. Major Disadvantage: Increases time. Besides the generations of all
1324. solutions, a comparison is made for each solution obtained.
1325. Another solution: another algorithm, but more "refined" than the combination of
the two. This is an algorithm that deals with artificial intelligence.
1326. Problem solved
1327. A vector with n whole number components is read. Let's get it only display odd
numbers in the positions of the vector.
1328. #include // to use cin and cout, include iostream.h 
1329. void main ()
1330. {
1331. int n, i, d, v [20]; // statements of variables
1332. cout << "n =" cin >> n; // read the number of elements in the vector, n
1333. for (i = 0; i 1334. vector v
1335. {
1336. cout << "v [" << i << "] =";
1337. cin >> v [i];
1338. }
1339. for (i = 0; i 1340. if ((i% 2 == 0) && (v [i]% 2 == 1)) // an element is tested if
1341. is par, if the remainder of the division at 2 is 0. The position is
1342. i, the element is v [i]
1343. cout << in [i] << ""; // I display the elements that respect both
1344. conditions
1345. }