POJ-3260 : The Fewest Coins

問題概要

N(<100)種類のコインが存在する。各コインの価値はv[i]で、それぞれをnum[i]枚ずつ持っている。T(<10000)円の商品が欲しい。こちらが出すコインの枚数とお釣りでもらうコインの枚数の和を最小化したい。ただし相手はコインを十分たくさん持っていて最小枚数でお釣りを支払う。無理なら指摘する。

解法

2*T位までコインの枚数制限ありと制限なしで最適な支払い枚数を計算しておく。コインの支払い枚数最小化の問題はナップサック問題の重さをコインの価値で置き換えて、価値を1で置き換えて、maxをminに置き換えるだけでよい。

acceptされたコード

#include <cstdio>
#include <deque>
using namespace std;

const int MAX_T = 20000;
const int MAX_N = 100;
const int INF = (int)(1.05e9); 

int N, T;
int values[MAX_N], nums[MAX_N];
int opt0[MAX_T + 1];
int opt1[MAX_T + 1];

void init() {
	scanf("%d%d", &N, &T);
	for (int i = 0; i < N; ++i) {
		scanf("%d", values + i);
	}
	for (int i = 0; i < N; ++i) {
		scanf("%d", nums + i);
	}
}

int solve() {
	fill(opt0, opt0 + MAX_T + 1, INF);
	fill(opt1, opt1 + MAX_T + 1, INF);
	opt0[0] = opt1[0] = 0;

	
	for (int i = 0; i < N; ++i) {
		for (int res = 0; res < values[i]; ++res) {
			SlideMinimizer sm(nums[i] + 1);
			for (int j = 0; j * values[i] + res <= MAX_T; ++j) {
				int val = opt0[j * values[i] + res] - j;
				opt0[j * values[i] + res] = sm.add(val) + j;
			}
		}
	}

	
	for (int i = 0; i < N; ++i) {
		for (int j = values[i]; j <= MAX_T; ++j) {
			updateMin(opt1[j], opt1[j - values[i]] + 1);
		}
	}

	int ans = INF;
	for (int i = T; i <= MAX_T; ++i) {
		updateMin(ans, opt0[i] + opt1[i - T]);
	}
	return ans == INF ? -1 : ans;
}

int main() {
	init();
	printf("%d\n", solve());

	return 0;
}