Informatika gyűjtemény

Egy szinttel feljebb kb_mal.cs

2004050607080910

<<  5. óra  >>

<<  Malac  >>

NézetNyomtat

kb_mal.cs (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 3 KB
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace Malac
{
    class Coin : IComparable<Coin>
    {
        public int weight;
        public int value;
    
        public int CompareTo(Coin other)
        {
            if (this.weight < other.weight) return -1;
            else
                if (this.weight > other.weight) return 1;
                else
                    return 0;
        }

        public Coin(int _v, int _w)
        {
            value = _v;
            weight = _w;
        }
    }

    class Program
    {
        private int[] cache; // adott összsúlynál mennyi a legkisebb érték (figyelem! index = súly)
        // -2 => ismeretlen
        // -1 => ismert, hogy nem lehet tovább folytatni az adott felosztást        

        private int n; // összsúly
        private int k; // különböző érmék száma.
        private List<Coin> coins;
        private int minWeight;

        public Program()
        {
            StreamReader ins = new StreamReader("malac8.be");
            StreamWriter outs = new StreamWriter("malac8.ki");
            string[] line = ins.ReadLine().Split(' ');

            n = int.Parse( line[0] );
            line = ins.ReadLine().Split(' ');
            k = int.Parse( line[0] );
            coins = new List<Coin>(k);
            cache = new int[n+1];
            for (int i = 0; i < k; i++)
            {
                line = ins.ReadLine().Split(' ');
                coins.Add(new Coin(int.Parse(line[0]), int.Parse(line[1])));
            }

            coins.Sort(); // súly szerint növekvőbe.

            minWeight = coins[0].weight;

            cache[0] = 0; // fontos jelentősége van, lásd lent!
            for (int i = 1; i <= n; i++)
            {
                cache[i] = -2; // init
            }

            outs.WriteLine( getMinValue(n) );
            outs.Close();
        }

        /**
         * n összsúlyra megállapítjuk a lehető legkisebb értéket.
         */
        private int getMinValue(int w)
        {
            if (cache[w] != -2) return cache[w]; // ha már van erre pontos értékünk.

            if (w < minWeight)
            {
                // ha a pillanatnyi összsúly kisebb, mint a lehető legkönnyebb érme súlya, akkor -1.
                cache[w] = -1;
                return cache[w];
            }

            int value, minValue = int.MaxValue, choosenCoin = -1;
            for (int i = 0; i < k; i++)
            {
                // megyünk sorra az érméken.
                if (coins[i].weight > w) break; // innentől kezdve tuti nincs jó megoldás.
                value = getMinValue(w - coins[i].weight);

                // value tartalmazza, hogy ha az adott érmét választjuk, akkor a maradék összsúly esetében mennyi a legkisebb
                // lehetséges érmék összértéke, nyilván ha a maradék összsúly 0, akkor 0 (ezért a cache[0] = 0)

                if (value != -1) // ha ez nem -1, hiszen az azt jelenti, hogy nem lehet folytatni
                {
                    // akkor az adott összsúlyból a value+(jelenlegi érme értéke) összértékű lehetséges érmét találtunk.
                    value += coins[i].value;
                    // ha ez minimális akkor megjegyezzük.
                    if (value < minValue)
                    {
                        minValue = value;
                        choosenCoin = i;
                    }
                }
            }

            // ha nem találtunk az adott összsúlyból semmilyen lehetséges felbontást (tehát az adott összsúly > legkisebb súly, de
            // a maradékot már nem tudjuk tovább bontani).
            if (choosenCoin == -1)
            {
                minValue = -1;
            }

            cache[w] = minValue;
            return cache[w];
        }

        static void Main(string[] args)
        {
            new Program();
        }
    }
}
(Vissza)