题目链接：https://vjudge.net/contest/126708#problem/H
题意：A有一大堆的硬币，他觉得太重了，想花掉硬币去坐的士；的士司机可以不找零，但是的士司机也不会多收零钱。怎么样才能使 A 花的零钱最多。
多重背包模板题
AC代码：
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main{
public static void main(String args[])
{
int N, M;
Scanner sc=new Scanner(System.in);
while(sc.hasNext())
{
N=sc.nextInt();
M=sc.nextInt();
if(N==&&M==) break;
int a[]=new int[];
int c[]=new int [];
int u[]=new int[];
for (int i=; i< N; i++) a[i]=sc.nextInt();
for (int i=; i< N; i++) c[i]=sc.nextInt();
int sun=;
boolean s[]=new boolean[];
s[]=true; for (int i=; i< N; i++)
{
Arrays.fill(u, );
for (int j=a[i]; j<=M; j++)
{
if (!s[j] && s[j-a[i]] && u[j-a[i]]< c[i])
{
s[j]=true;
u[j]=u[j-a[i]]+;
sun++;
}
}
}
System.out.println(sun);
} }
}
class Scanner {
BufferedReader br;
StringTokenizer st; Scanner(InputStream in) {
br = new BufferedReader(new InputStreamReader(in));
eat("");
} private void eat(String string) {
st = new StringTokenizer(string);
} String nextLine() {
try {
return br.readLine();
} catch (IOException e) {
return null;
}
} boolean hasNext() {
while (!st.hasMoreTokens()) {
String s = nextLine();
if (s == null)
return false;
eat(s);
}
return true;
} String next() {
hasNext();
return st.nextToken();
} int nextInt() {
return Integer.parseInt(next());
} long nextLong() {
return Long.parseLong(next());
} double nextDouble() {
return Double.parseDouble(next());
}
}