paizaラーニングレベルアップ問題集の「お菓子の詰め合わせ」をやってみた

paiza×Qiita記事投稿キャンペーンということで、paizaラーニングレベルアップ問題集のお菓子の詰め合わせをやってみました。

---

ビット全探索

お菓子の種類数だけ買う、買わないの選択の仕方は、全部で$2^N$通りあります。
買う、買わないの選択の仕方は、bitmaskによる集合表現を用いることができます。

（例）$N=3$の場合

#	A	B	C	2進法
0	×	×	×	000
1	○	×	×	001
2	×	○	×	010
3	○	○	×	011
4	×	×	○	100
5	○	×	○	101
6	×	○	○	110
7	○	○	○	111

左右が逆になりましたが、お菓子Aを買うことを二進法の最下位ビット（一番右の桁）を$1$にすることで表し、お菓子Aを買わないことを二進法の最下位ビットを$0$にすることで表します。この○×を全部で$2^N$通りループさせます。$2^N$は、多くの言語でシフト演算を用いて1<<Nと書くことができます。

n=(入力値を整数変換)
N=1<<n //2のn乗
for(i=0;i<N;i++){
    for(j=0;j<n;j++){
        if((i&(1<<j))!=0){//j番目のお菓子を買う。&はビット演算子and
            //└if(((i>>j)&1)==1) でも可
        }
    }
}

---

今回は、C言語で清書していきます。

#include <stdio.h>

int main() {
	int n, x;
	scanf("%d %d", &n, &x);
	int price[n];
	for (int i = 0; i < n; i++)
		scanf("%d", &price[i]);
	int N = 1 << n;
	int max_count = 0; // お菓子の最大種類数
	int max_total = 0; // 最大の金額（お釣りが最小）
	for (int i = 0; i < N; i++) {
		int count = 0;
		int total = 0;
		for (int j = 0; j < n; j++) {
			if ((i & (1 << j)) != 0) { // j番目のお菓子を買う
				count += 1;
				total += price[j];
			}
		}
		if (total <= x) { // お菓子の総額が指定範囲内に収まっている
			if (count > max_count) {
				max_count = count;
				max_total = total;
			} else if (count == max_count && total > max_total) {
				max_total = total;
			}
		}
	}
    
    // お釣り
	int change = x - max_total;
	printf("%d\n", change);
	return 0;
}

---

種類の最大数を求める

問題文に「お釣りを最小にすることよりも種類の数を最大にすることを優先する」とあります。実は、最大の種類の数を予め求めることができて（最大種類数を$M$種類とします）、あとは再帰関数で$M$重ループを実現してお釣りを最小（購入金額を最大）にします。
最大の種類の数は、お菓子の値段の安い順に買うことを考えることにより求められます。

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *p, const void *q) {
	int a = *(int*) p;
	int b = *(int*) q;
	if (a < b)
		return -1;
	if (a > b)
		return 1;
	return 0;
}

int chmax(int *dst, int src) {
	if (src > *dst)
		*dst = src;
	return *dst;
}

// m種類のお菓子を買う時の、指定範囲内xの最大の金額
int max_total(int n, const int *price, int x, int m, int k, int *indices,
		int total) {
	if (k == m) {
		if (total <= x)
			return total;
		return -1;
	}
	int result = 0;
	for (int i = (k ? indices[k - 1] + 1 : 0); i < n; i++) {
		indices[k] = i;
		chmax(&result,
				max_total(n, price, x, m, k + 1, indices, total + price[i]));
	}
	return result;
}

int main() {
	int n, x;
	scanf("%d %d", &n, &x);
	int price[n];
	for (int i = 0; i < n; i++)
		scanf("%d", &price[i]);
    
    // お菓子の値段昇順ソート
	qsort(price, n, sizeof(price[0]), cmp);

    // お菓子の最大種類数mを求める
	int total = 0;
	int m = 0;
	while (m < n) {
		total += price[m];
		if (total > x)
			break;
		m++;
	}

	int indices[m];
	int change = x - max_total(n, price, x, m, 0, indices, 0);
	printf("%d\n", change);
	return 0;
}

---

動的計画法

$\text{dp}_i[x]:=(i$種類の中から合計$x$円のお菓子を買う最大種類数$)$
とすると、答えは

X-\max\{x|\text{dp}_n[x]=\max_x\text{dp}_n[x]\}

となります。但し、$i$種類の中から合計$x$円のお菓子を買う組み合わせがない場合、$\text{dp}_i[x]=-1$としておきます。

#include <stdio.h>
#include <string.h>

// 最大値を更新する（一応、最大値を返す）
int chmax(int *dst, int src) {
	if (src > *dst)
		*dst = src;
	return *dst;
}

int main() {
	int n, x;
	scanf("%d %d", &n, &x);
	int price[n];
	for (int i = 0; i < n; i++)
		scanf("%d", &price[i]);

    // 丁度y円のお菓子を買う最大種類数
	int dp[x + 1];

    // -1（丁度y円のお菓子を買う組み合わせがない状態を表す）で初期化
	memset(dp, -1, sizeof(dp));

    // 合計0円のお菓子の最大種類数を0で初期化
	dp[0] = 0;

	int max_count = 0;
	int max_total = 0;
	for (int i = 0; i < n; i++) {
		for (int j = x; j >= price[i]; j--) { // 後ろから更新
			if (dp[j - price[i]] >= 0) {
				chmax(&dp[j], dp[j - price[i]] + 1);

                // 最大種類数、最大金額を更新
				if (dp[j] > max_count) {
					max_count = dp[j];
					max_total = j;
				} else if (dp[j] == max_count && j > max_total) {
					max_total = j;
				}
			}
		}
	}

    // お釣り
	int change = x - max_total;
	printf("%d\n", change);
	return 0;
}