グレースケールアルゴリズム

グリディアルゴリズム、貪欲アルゴリズムは最適解を求める方法である.
問題の最適化に使用する最大または最小の解を探します.
多くの場合、どちらかを選ぶたびに、その瞬間に自分が一番適当だと思っているものを選び、外に出るようにして答えを出す.
各選択点の決定は地域的に最良であるが、これらの選択を収集し続け、最終的に答えを出すと、それが最良であることは保証されない.
一度選ばれたら、後悔しない.そのため、大部分탐욕 알고리즘들은 단순하며, 또한 제한적인 문제들에 적용된다.

金をさがす

代表的な質問でお金を探します.

물건값: 1200원
받은돈: 2000원
거스름돈: 800원

이 때 거스름돈으로 주는 최적해는 500원 1개, 100원 3개이다

https://www.acmicpc.net/problem/14916
おつりの問題で解決しましょう.

public class boj_14916 {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int cnt = 0;
        boolean isAns = false;
        while(n >= 0){
            // 5로 나누어 떨어지면 바로 답 출력
            if(n % 5 == 0){
                System.out.println(cnt + n/5);
                isAns = true;
                break;
            }
            // 안되면 2씩 뺀다
            n -= 2;
            cnt++;
        }
        if(!isAns){
            System.out.println(-1);
        }
    }
}

2を減算し続け、5を減算すると、答えが出力されます.反復文条件はn>0ではなく、n>=0の原因はお金を探すためであり、nが0になるとif(n%5=0)条件に遭遇する.繰り返し文では,nが0でなければ5と2を組み合わせることができないため,isAnsを用いて不可能な場合に−1を出力する.
他のブログで大発の簡単なコードを見つけて共有します.
https://foxtrotin.tistory.com/319

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int cnt = 0;
        if(n == 1 || n == 3){
            System.out.println(-1);
            return;
        }
        if(n % 5 % 2 == 0){
            cnt = n / 5 + n % 5 / 2;
        }else{
            cnt = n / 5 + (n%5 + 5)/2 - 1
        }
        System.out.println(cnt);
    }

5と2を分けたら、あと5元で有利なので、先に分けて、残りのお金は2を探します.
このコードはcnt = n/5 + n%5/2nは6,13のようにお互いを区別せず、これを理解するのは難しい.
nを5で割った残数は0,1,2,3,4である
残りが2,4なら、探した5の残りを全部2にするので、n%5/2を加えればいいです.
n=9の場合(거스름돈/5) + (거스름돈%5/2) = 1+2 = 3残りが1、3なら2に分けられないので、5円玉を1つ少なくして6、8にして2に分けます.
例えば、n=13は5元1個、2元4個、5個が答えである.(거스름돈/5 - 1) + (거스름돈%5 + 5)/2 - 1= 1+4-1 = 4

リュックサックの梱包(Knapsack)

これは何度も聞いたことのある質問です.泥棒は盗んだものをリュックサックに入れようとしたが、リュックサックの重さは限られており、物の重さと価値は固定されている.このとき盗んだ品物の価格が最大の問題です.

배낭 무게: 30kg
물건1: 25kg, 10원
물건2: 10kg, 9원
물건3: 10kg, 5원

答え:東西2+物件3=9元+5元=14元が答えです.
(仮に1つのものしかないとします)
Knapsackには2つのタイプがあり、最適な貪欲法を求めるにはFractionalリュックサックしか使えません.0-1リュックサックはdpで解くことができます.

0-1 Knapsack

物が割れない

Fracktional Knapsack
*分割できるものは/457916、
Fractionalリュックサックの時は簡単に考えて、リュックサックにもっと高いものを入れればいいです.
それなら1キロ当たりの価格でリュックの重さを計算すればいいです.リュック30キロの時
モノ1(50)+モノ3(140)+モノ2の半分(30)=220万円が正解