解いてみた。「Aランク：お菓子の詰め合わせ」

問題

「Aランク：お菓子の詰め合わせ」

コード

Javaで解いてみました。

import java.util.*;

public class Main {
    private static final int MAX_VAL = 99999;
    private static final int MIN_VAL = 0;
    
    private static int nN;
    private static int nX;
    private static int[] anx;

    private static int nMaxKind;
    private static int nMinChange;
    
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        
        // 事前準備
        nN = sc.nextInt();
        nX = sc.nextInt();
        
        anx = new int[nN];
        for (int i = 0; i < nN; i++) {
            anx[i] = sc.nextInt();
        }

        nMaxKind = MIN_VAL;
        nMinChange = MAX_VAL;
        
        // 商品購入開始
        func(0, 0, 0);  
        
        // 結果出力
        System.out.println(nMinChange);
    }
    
    private static void func(int n, int kind, int sum) {
        if (n >= nN) {
            int nChange = nX - sum;
            if (nChange < 0) { return; }
            
            if (kind > nMaxKind) {
                nMaxKind = kind;
                nMinChange = nChange;
            } else if (kind == nMaxKind) {
                if (nMinChange > nChange) {
                    nMinChange = nChange;
                }
            }
            
            return;
        }
        
        func(n+1, kind, sum);           // 商品nを買わなかった場合
        func(n+1, kind+1, sum+anx[n]);  // 商品nを買った場合
    }
}

解説

標準入力からの数値の読み取り

Scanner インスタンスを作り、nextInt()メソッドで数値を取得しています。
使用する変数は、グローバル変数的に使用したいので、基本、クラスのメンバ変数として定義しています。

func()メソッドの処理

n < N の場合

次の2つの場合について、func()メソッドを呼び出します。

• n番目の商品を買わなかった場合、nだけ１増やして、商品の種類k、合計額sはそのまま、func()メソッドに渡す
• n番目の商品を買った場合、nを１増やし、商品の種類kも１増やす。合計額に商品の値段anx[n]を足し、func()メソッドに渡す

n = N の場合

終了処理として、以下の判定を行います。

• 購入合計額がXを超えていたら、何もしない。
• 購入した種類が、暫定種類最大値より大きい場合、暫定種類最大値と、暫定最小釣銭を、現在の値で更新する
• 購入した種類が、暫定種類最大値と等しい場合、お釣りが暫定最小釣銭より小さければ、暫定最小釣銭を更新する