题目：
现有n1+n2种面值的硬币，其中前n1种为普通币，可以取任意枚，后n2种为纪念币，每种最多只能取一枚，每种硬币有一个面值，问能用多少种方法拼出m的面值？
输入描述:
第一行三个整数n1, n2, m，分别表示普通币种类数，纪念币种类数和目标面值
第二行n1个整数，第i种普通币的面值a[i]。保证a[i]为严格升序。
第三行n2个整数，第i种纪念币的面值b[i]。保证b[i]为严格升序。
对于30%的测试，保证1<=n1+n2<=10，1<=m<=100，1<=a[i]<=100 1<=b[i]<=100
对于100%的测试，保证1<=n1+n2<=100, 1<=m<=100000, 1<=a[i]<=100000 1<=b[i]<=100000
输出描述:
输出一行，包含一个数字x，表示方法总数对1000000007（1e9+7）取模的结果。
注意：不要忘记取模！
示例1
输入
3 1 5
1 2 3
1
输出
9
说明： (x)代表面值为x的普通币，[x]代表面值为x的纪念币，样例所有方法数如下：
(1)(1)(1)(1)(1)
(1)(1)(1)(2)
(1)(1)(3)
(1)(2)(2)
(2)(3)
(1)(1)(1)(1)[1]
(1)(1)【1】(2)
(1)【1】(3)
【1】(2)(2)
备注:
两个方法，它们任意一种或以上的硬币数量不同，则认为是两种拼法。
分析：
背包问题：给定一组固定价值和固定重量的物品以及一个已知最大承重量的背包，求在不超过最大承重量的前提下，能放进背包里面的物品的最大总价值；
0-1背包：每种物品都有一件，可以选择放入或不放入；
完全背包问题：每种物品都有无限件；
多重背包：限定每一种物品的个数(如，商品A有5件，商品B有4件)
动态规划实现，遵循"贪心的原则",普通币为完全背包问题，从小到大依次放入，纪念币为0-1背包问题，从大到小依次放入；
设计一维数组f[i]，其中i表示当前背包中的价值，f[i]表示价值为i出现的可能性情况数，参考动态规划的思想，对上边输入进行分析，假设当前可选的价值为2(普通币),f[3]=f[3]+f[3-2](即当前f[3]的种类数等于可选价值为1时f[3] 的可选情况数+在固定选一个价值为2时，剩余价值的可选情况)
代码实现：
package com.bj.zijietiaodong;
import java.util.Scanner;
/**
* 拼硬币
*
*/
public class Test1 {
public static void main(String[] args) {
//1.读取数据
Scanner scan = new Scanner(System.in);
String str1 = scan.nextLine();
String str2 = scan.nextLine();
String str3 = scan.nextLine();
scan.close();
String str1_arr[] = str1.split(" ");
String str2_arr[] = str2.split(" ");
String str3_arr[] = str3.split(" ");
int num1 = Integer.parseInt(str1_arr[0]);
int num2 = Integer.parseInt(str1_arr[1]);
int sum = Integer.parseInt(str1_arr[2]);
int f [] = new int[10010];
f[0] = 1;
//完全背包问题(从小到大枚举容量)(f[i]为当前背包重量为i时的可能种类数)
for (int i = 0; i <num1; i++) {
for (int j = Integer.parseInt(str2_arr[i]); j <=sum; j++) {
/ /上一层的情况+当前的情况数
f[j]+=f[j-Integer.parseInt(str2_arr[i])];
}
}
//0-1背包问题(从大到小枚举容量)
for (int i = 0; i <num2; i++) {
for (int j = sum;j>=Integer.parseInt(str3_arr[i]); j--) {
f[j]+=f[j-Integer.parseInt(str3_arr[i])];
}
}
if(f[sum]>1e9+7)
System.out.println(f[sum]%1e9+7);
else
System.out.println(f[sum]);
}
}
结果：
3 1 5
1 2 3
1
9
知识点：
1.需要熟悉基本的算法思想，如贪婪法、动态规划、分治法以及解空间的穷举搜索；
2.问题的合理转化(用算法思想解决实际问题);
参考网址：
网友评论