Interesting Dart Game（鸽巢原理+完全背包）

题目链接：https://cn.vjudge.net/problem/ZOJ-2955

Recently, Dearboy buys a dart for his dormitory, but neither Dearboy nor his roommate knows how to play it. So they decide to make a new rule in the dormitory, which goes as follows:

Given a number N, the person whose scores accumulate exactly to N by the fewest times wins the game.

Notice once the scores accumulate to more than N, one loses the game.

Now they want to know the fewest times to get the score N.

So the task is :
Given all possible dart scores that a player can get one time and N, you are required to calculate the fewest times to get the exact score N.

Input

Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 50) which is the number of test cases. And it will be followed by T consecutive test cases.

Each test case begins with two positive integers M(the number of all possible dart scores that a player can get one time) and N. Then the following M integers are the exact possible scores in the next line.

Notice: M (0 < M < 100), N (1 < N <= 1000000000), every possible score is (0, 100).

Output

For each test case, print out an integer representing the fewest times to get the exact score N.
If the score can't be reached, just print -1 in a line.

Sample Input

Sample Output

2
3
-1

这个题给我们的感觉就是完全背包但是N太大需要用鸽巢原理优化

在鸽巢原理的介绍里面，有例题介绍：设a1,a2,a3,……am是正整数的序列，试证明至少存在正数k和l，1<=k<=l<=m,是的和ak+ak+1+……+al是m的倍数，接下来开始证明：

构造一个序列s1=a1,s2=a1+a2，……，sm=a1+a2+……+am,那么会产生两种可能：

1：若有一个sn是m的倍数，那么定理成立：

2：假设上述的序列中没有任何一个元素是m的倍数，令rh ≡ sh mod m;其中h=1,2,……,m;我们已知上面的所有项都非m的倍数，得到s1模m的余数是r1,s2模m的余数是r2,同理往下类推，r是一个余数序列，在这里所有的余数都不为0，因为假设是不存在有m的倍数的，所以r序列的元素小于m，根据抽屉原理（鸽巢原理），m个余数在[1,m-]区间里的取值至少存在一对rh,rl，并且满足 rh=rk,即sh和sk满足

sk ≡ sh mod m，那么假设h>k，得到

sh-sk = (a1+a2+……+ah) - (a1+a2+……+ak)

sh - sk =ak+1 +ak+2 +……+ah ≡ 0 mod m（此处的k是序列a的下标）

证明到此结束；

先将a(1---n)排序

(a1,a2,a3.......an) 每个数选择的个数为(k1,k2,k3........kn)(ki可以为0)

使得 k1*a1+k2*a2+k3*a3+.........+kn*an==N

则 (k1+k2+k3+.....kn-1)<an

用反证法证明：假如说sum= (k1+k2+k3+.....kn-1)>=an 那么根据鸽巢原理在前sum个数里面一定存在连续的几个数(ai---aj)之和为an的倍数

那么用一定数量的an代替这几个数(ai----aj) 一定更优

所以(k1+k2+k3+.....kn-1)<an 成立

所以前(n-1)个数的数量之和最多也得小于an(100) 前(n-1)个数的和小于10000 然后对前(n-1)个数进行背包再枚举就可以了

https://www.cnblogs.com/liulangye/archive/2013/03/13/2958326.html

https://blog.csdn.net/yitiaodacaidog/article/details/22691069

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<list>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e4+5;
const int INF=0x3f3f3f3f;
int a[105],dp[N];
int main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		int V=10000;
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=1; i<=n; i++)
			scanf("%d",&a[i]);
		sort(a+1,a+1+n);
		for(int i=1; i<=V; i++) {
			dp[i]=INF;
		}
		dp[0]=0;
		int ans=INF;
		for(int i=1; i<n; i++) {
			for(int v=a[i]; v<=V; v++) {
				dp[v]=min(dp[v],dp[v-a[i]]+1);
			}
		}
		for(int i=0; i<=V; i++) {
			if(dp[i]!=INF&&(m-i)%a[n]==0)
				ans=min(ans,dp[i]+(m-i)/a[n]);
		}
		if(ans==INF) printf("-1\n");
		else printf("%d\n",ans);
	}
	return 0;
}