poj 1252 zoj 1558 Euro Efficiency 完全背包

雷同poj 3260

//看不懂题目，百度，发现题意如此，完全背包，计算方案数
//大意：六种货币，面值都小于100。用这六种货币（可加可减）
//用最少的货币数组成1到100。求出这1到100中最大的，并求平均值。
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
const int INF = 20000000;
const int MAXV = 100 * 100 + 100 + 1;	//方案数最多为100种，可推出MAXV
int f[MAXV];
int a[6];
int main() {
	//freopen("1.txt", "r", stdin);
	int t;
	cin >> t;
	while(t--) {
		for(int i = 0; i < 6; i++)
			cin >> a[i];
		int maxV = a[5] * 100 + 100;
		for(int i = 0; i <= maxV; i++)
			f[i] = INF;
		f[0] = 0;
		//先不算找钱，看有多少解决方案
		for(int i = 0; i < 6; i++) {
			for(int j = a[i]; j <= maxV; j++) {
				f[j] = min(f[j], f[j - a[i]] + 1);
			}
		}
		//加上找钱的，由于是找钱
		//f[m][n] = min(f[m][n], f[m - 1][n + value] + 1);
		//若用一维，则需要逆序，才能保证满足完全背包
		for(int i = 0; i < 6; i++) {
			for(int j = maxV - a[i]; j >= 0; j--) {
				f[j] = min(f[j], f[j + a[i]] + 1);
			}
		}
		int tot = f[1];
		int _max = f[1];
		for(int i = 2; i <= 100; i++) {
			if(f[i] != INF) {			//其实不用判断，因为肯定有价值为1的，保证每一个都有方案
				tot += f[i];
				_max = max(_max, f[i]);
			}
		}
		float ave = tot / 100.0;
		printf("%.2f %d/n", ave, _max);
	}
 	return 0;
}