Problem Statement
Takahashi has N kinds of coins; specifically, for 1≤i≤N, he has B i coins worth A i yen (the currency in Japan) each.
Determine if Takahashi can pay exactly X yen (without change) with the coins he currently has.
高桥有 N 种硬币;具体来说,对于 1≤i≤N,他有 B i 枚硬币,每枚价值 A i 日元(日本货币)。确定高桥是否能用他目前拥有的硬币支付 X 日元(不找零)。
Constraints
1≤N≤50
1≤X≤10 4
1≤A i ≤100 1≤B i ≤50 A i are pairwise distinct.
All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N
X
A 1 B 1 A 2 B 2 ⋮A N B N
Output
Print Yes if Takahashi can pay exactly X yen with the coins he currently has; print No otherwise.
Sample Input 1
2 19
2 3
5 6
Sample Output 1
Yes
Takahashi has three 2-yen coins and six 5-yen coins. He can use two 2-yen coins and three 5-yen coins to pay exactly 2×2+5×3=19 yen. Thus, Yes should be printed.
Sample Input 2
2 18
2 3
5 6
Sample Output 2
No
There is no combination of the coins that he can use to pay exactly
18 yen. Thus, No should be printed.
Sample Input 3
3 1001
1 1
2 1
100 10
Sample Output 3
Yes
He need not use all kinds of coins.
构造一个数组,然后每次去更新能达到的最长的位置,也就是能换成多少钱。
然后每次重新更新数组。最后判断canPay[n]是true or false。
-------------
import java.util.Scanner;
public class Abc286 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int x=sc.nextInt();
boolean[]canpay=new boolean[x+1];
canpay[0]=true;
while (n-->0) {
int a=sc.nextInt();
int b=sc.nextInt();
boolean[]next=new boolean[x+1];
for (int i = 0; i <=x; i++) {
for (int j = 0; j <=b&&i+a*j<=x; j++) {
next[i+a*j]=next[i+a*j]|canpay[i];
}
}
canpay=next;
}
System.out.println(canpay[x]?"Yes":"No");
sc.close();
}
}