[yukicoder] No.617 Nafmo、買い出しに行く
全数探索の問題
No.617 Nafmo、買い出しに行く - yukicoder
この問題は全数探索をすることで解くことができると思います。つまり、すべての商品の選び方を元に重さを計算します。重さが になればその時点で解が見つかりますが、そうでない場合は全ての組み合わせを調べる必要があります。
組み合わせの列挙ですが、これは前に記事にしたビット列の列挙のコードを利用することで実現できます。
コード
import java.util.Arrays; import java.util.Scanner; public class Exec0617 { public static int [] A; public static int K; public static int max = 0; public static void main(String[] args) { Scanner scan = new Scanner(System.in); int N = scan.nextInt(); K = scan.nextInt(); A = new int[N]; for(int i = 0; i < N; i++) { A[i] = scan.nextInt(); } scan.close(); int []S = new int[N]; Arrays.fill(S, 0); rec(0, N, S); System.out.println(max); } public static void rec(int k, int n, int[] S) { if(k == n) { solve(S); return; } rec(k + 1, n, S); S[k] = 1; rec(k + 1,n, S); S[k] = 0; } public static void solve(int[] S) { //disp(S); int sum = 0; for(int i = 0; i < S.length; i++) { if(S[i] == 1) { sum += A[i]; } if(sum > K) { break; }else if(sum == K) { System.out.println(K); System.exit(0); }else { if(max < sum) { max = sum; } } } } public static void disp(int []A) { for(int i = 0; i < A.length - 1; i++) { System.out.print(A[i] + ", "); } System.out.println(A[A.length -1]); } }
disp()メソッドは使っていませんが、正しいビット列を出力しているかを調べるために使いました。