Pernyataan Masalah

Berdasarkan sekumpulan denominasi koin dan jumlah target, tentukan jumlah minimum koin yang diperlukan untuk memenuhi jumlah tersebut.

Tutorial Greedy Algorithms Javascript Dan Penjelasan
Tutorial Greedy Algorithms Javascript Dan Penjelasan


Pendekatan:

Pendekatan serakah untuk masalah Perubahan Koin melibatkan pemilihan koin terbesar pada setiap langkah hingga jumlah sisanya menjadi nol.


JavaScript Code:

function greedyCoinChange(coins, amount) {

  // Sort coins in descending order

  coins.sort((a, b) => b - a);


  let coinCount = 0;

  let remainingAmount = amount;


  for (let i = 0; i < coins.length; i++) {

    const currentCoin = coins[i];


    // Calculate how many times the current coin can be used

    const numCoins = Math.floor(remainingAmount / currentCoin);


    // Update the count of coins used

    coinCount += numCoins;


    // Update the remaining amount

    remainingAmount -= numCoins * currentCoin;


    // Break the loop if the remaining amount becomes zero

    if (remainingAmount === 0) {

      break;

    }

  }


  // If the remaining amount is not zero, it means it cannot be made with the given coins

  if (remainingAmount !== 0) {

    return "Cannot make change with the given coins.";

  }


  return coinCount;

}


// Example Usage

const coins = [25, 10, 5, 1]; // Coin denominations in cents

const targetAmount = 63; // Target amount in cents


const result = greedyCoinChange(coins, targetAmount);

console.log(`Minimum number of coins needed: ${result}`);



Penjelasan:

  1. Fungsi greedyCoinChange mengambil serangkaian denominasi koin (koin) dan jumlah target (jumlah) sebagai input.
  2. Ini mengurutkan denominasi koin dalam urutan menurun, karena kami ingin menggunakan koin terbesar terlebih dahulu.
  3. Ia kemudian mengulangi koin-koin yang telah diurutkan, menghitung berapa kali setiap koin dapat digunakan untuk menambah jumlah sisanya.
  4. Jumlah total koin yang digunakan diperbarui, dan jumlah sisanya dikurangi.
  5. Perulangan berlanjut hingga jumlah yang tersisa menjadi nol atau hingga semua denominasi koin dipertimbangkan.
  6. Jika jumlah yang tersisa tidak nol setelah putaran, berarti jumlah target tidak dapat dicapai dengan koin yang diberikan.

Catatan: Meskipun algoritme serakah bekerja dengan baik untuk beberapa masalah, algoritme tersebut mungkin tidak selalu memberikan solusi optimal untuk semua skenario. Penting untuk menganalisis masalah dan memahami kondisi di mana pendekatan serakah dapat dilakukan.


Baca Juga: