package algoritmit2;

import java.util.Random;

/**
 * Algoritmit 2 -kurssin neljännen ohjelmointitehtävän ratkaisu, joka ratkaisee kapsäkkiongelman taulukoimalla.
 * @author Saku
 * @version 28.4.2017
 *
 */
public class Kapsakki {
    Tavara[] tavarat;
    int lkm = 10; // Perusjoukossa olevien tavaroiden lukumäärä.
    int kokonaispaino = 20;

    /**
     * Ohjelmaa testaava pääluokka.
     * @param args Ei käytössä.
     */
    public static void main(String[] args){
        Kapsakki k = new Kapsakki();
        k.alustaTavarat();


        int vastaus = k.s( k.tavarat.length -1 , k.kokonaispaino);
        k.tulostaTavarat();
        System.out.println("Kapsäkkiin(, jonka kokonaispainoraja on " + k.kokonaispaino + ") mahtuvista tavaroista kertyvä suurin hyötyarvo: " + vastaus);

        System.out.println("");

        k.kokonaispaino = 100; // Nyt laukkuun mahtuvat kaikki tavarat, joten hyötyarvo on sama, kuin tavaroiden yhteishyötyarvo.
        vastaus = k.s( k.tavarat.length -1 , k.kokonaispaino);
        k.tulostaTavarat();
        System.out.println("Kapsäkkiin(, jonka kokonaispainoraja on " + k.kokonaispaino + ") mahtuvista tavaroista kertyvä suurin hyötyarvo: " + vastaus);

    }


    /**
     * Tulostaa perusjoukossa olevien tavaroiden painot ja hyötyarvot.
     */
    private void tulostaTavarat(){
        System.out.println("Perusjoukosta löytyvät tavarat: ");
        int painoYht = 0;
        int hyotyYht = 0;
        for(int i = 0; i < tavarat.length; i++){
            System.out.println("Tavaran " + (i + 1)+ " paino on: " + tavarat[i].paino + " ja hyötyarvo: " + tavarat[i].hyoty );
            painoYht += tavarat[i].paino;
            hyotyYht += tavarat[i].hyoty;
        }
        System.out.println("Tavaroiden yhteispaino on: " + painoYht);
        System.out.println("Tavaroiden yhteishyötyarvo on: " + hyotyYht);
    }


    /**
     * Metodi, joka laskee kapsäkkiin mahtuvien tavaroiden maksimaalisen hyötyarvon.
     * @param k joukon koko, josta tavaroita tutkitaan.
     * @param r Kapsäkin kokonaispainoraja.
     * @return Suurin laukkuun mahtuva hyötyarvo.
     */
    private int s(int k, int r) {
        if(k < 0 || r <= 0){
            return 0;
        }

        if(tavarat[k].paino > r){
           return s(k-1, r);
        }
        return Math.max(s(k-1, r), tavarat[k].hyoty + s(k-1, r - tavarat[k].paino));



    }


    /**
     * Alustaa perusjoukon tavarat satunnaisilla arvoilla.
     */
    private void alustaTavarat() {
        tavarat = new Tavara[lkm];
        Random r = new Random();
        for(int i = 0; i < lkm; i++){
           tavarat[i] = new Tavara((r.nextInt(10)+1), (r.nextInt(10)+1) );
       }
    }



    /**
     * Tavara luokka, jonka esiintymillä kapsäkki täytetään.
     *
     */
    public static class Tavara {
            int paino = 0;
            int hyoty = 0;

            /**
             * Tavaran muodostaja -metodi.
             * @param w tavaran paino
             * @param p tavaran hyötyarvo
             */
            public Tavara(int w, int p ){
                this.paino = w;
                this.hyoty = p;
            }
        }


}