输入为两行:
第一行为两个正整数n(1 ≤ n ≤ 1000),sum(1 ≤ sum ≤ 1000)
第二行为n个正整数A[i](32位整数),以空格隔开。
输出所求的方案数
5 15 5 5 10 2 3
4
import java.util.Arrays; import java.util.Scanner; public class GetTheSum { public static void main(String[] args) { //testIt(); Scanner scanner = new Scanner(System.in); int i = 0; String[] lines = new String[2]; while (i <= 1 && scanner.hasNextLine()) { lines[i] = scanner.nextLine(); i++; } String[] nAndSum = lines[0].split("\\s+"); int n = Integer.parseInt(nAndSum[0]); int sum = Integer.parseInt(nAndSum[1]); int[] arr = Arrays.stream(lines[1].split("\\s+")).mapToInt(Integer::parseInt).toArray(); long count = solve(sum, arr); //System.out.println("sum=" + sum + ", arr=" + Arrays.toString(arr) + ", count=" + count); System.out.println(count); } // target: [0, 1000] // values.length: [1, 1000] public static long solve(int target, int[] values) { int iCount = values.length + 1; int jCount = target + 1; // dp[i][j] // 在 数组前i个数字 中任选组合,使得加和为j时,方案的最大个数为 dp[i][j] long[][] dp = new long[iCount][jCount]; for (int j = 0; j < jCount; j++) { // 在 数组前1个数字 中任选组合,使得加和为j时,方案的最大个数为 dp[1][j] dp[1][j] = (values[0] == j) ? 1 : 0; } // 在 数组前i个数字 中任选组合 for (int i = 2; i < iCount; i++) { int val = values[i - 1]; //使得加和为j for (int j = 1; j < jCount; j++) { // 不使用i时,就可以加和为j 的方案个数 dp[i][j] = dp[i - 1][j]; if (j == val) { // 单单 values[i - 1] 就正好形成了一种方案 dp[i][j] = dp[i][j] + 1; // 不使用i时,可以加和为 0 的方案个数 long tmp = dp[i - 1][0]; dp[i][j] = dp[i][j] + tmp; } else if (j > val) { // 不使用i时,可以加和为 j-values[i-1] 的方案个数 long tmp = dp[i - 1][j - val]; dp[i][j] = dp[i][j] + tmp; } // values[i - 1]本身就已经 > j 了,任何方案都无法使用 values[i - 1] 啦 else { } } } return dp[values.length][target]; } public static void testIt() { int sum = 15; int[] arr = new int[]{5, 5, 10, 2, 3}; long count = solve(sum, arr); System.out.println("sum=" + sum + ", arr=" + Arrays.toString(arr) + ", count=" + count); } }
动态规划
设m[i][j]是前i个数 和为j的的最大组合方案数
递归公式
1 j=0 //j-a[i]为0时,表示a[i]=j,组合数为1
0 j<0
0 i<1且j!=0
M[i][j]=M[i-1][j]+M[i-1][j-a[i]] //前i-1个 和为j的最大组合数 + 前i-1个 和为 j-a[i]的最大组合数
例如 n=7 sum=8
数据为:5 1 2 4 3 2 3
得到如下矩阵
(i\j) 0 1 2 3 4 5 6 7 8
0 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 1 0 0 0
2 1 1 0 0 0 1 1 0 0
3 1 1 1 1 0 1 1 1 1
4 1 1 1 1 1 2 2 2 1
5 1 1 1 2 2 3 3 3 3
6 1 1 2 3 3 5 5 6 6
7 1 1 2 4 4 7 8 9 11
例如:m[7][9]=m[6][8]+m[6][8-3]=11
由于当前行只用到了上一行的数值,固可用二维数组存储
public static void main(String[] args)throws Exception{
BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
String[] strings=br.readLine().split("\\s");
int n=Integer.parseInt(strings[0]);
int sum=Integer.parseInt(strings[1]);
strings=br.readLine().split("\\s");
int[]data=new int[n];
for(int i=0;i<n;i++){
data[i]=Integer.valueOf(strings[i]);
}
dp(n,sum,data);
}
private static void dp(int n,int sum,int [] data){
long[][] m=new long[2][sum+1];
m[0][0]=1;//j=0
m[1][0]=1;//j=0
for(int i=1;i<=n;i++){
for(int j=1;j<=sum;j++){
if(j>=data[i-1]){
m[1][j]=m[0][j]+m[0][j-data[i-1]];
}else {
m[1][j]=m[0][j];
}
}
// System.out.println(Arrays.toString(m[0]));
for(int k=0;k<=sum;k++){
m[0][k]=m[1][k];
}
}
// System.out.println(Arrays.toString(m[0]));
System.out.println(m[0][sum]);
}
import java.util.Scanner;
public class Main {
public static long numberOfMethod(int[] A, int sum){
long[] dp = new long[sum + 1]; //这里用long类型,用int只能80%
dp[0] = 1;
for (int i : A){
for (int j = sum; j >= i; j--){
dp[j] += dp[j - i];
}
}
return dp[sum];
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while (sc.hasNext()){
int n = sc.nextInt();
int sum = sc.nextInt();
int[] A = new int[n];
for (int i = 0; i < n; i++){
A[i] = sc.nextInt();
}
System.out.println(numberOfMethod(A, sum));
}
sc.close();
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int sum = scanner.nextInt();
int[] arr = new int[n+1];
for (int i = 1; i <= n; i++) {
arr[i] = scanner.nextInt();
}
System.out.println(calculate(arr, n, sum));
}
public static long calculate(int[] arr, int n, int sum) {
long[][] dp = new long[n+1][sum + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= sum; j++) {
if (j >= arr[i])
dp[i][j] = dp[i-1][j] + dp[i-1][j-arr[i]];
else
dp[i][j] = dp[i-1][j];
}
}
return dp[n][sum];
}
}
//不是很理解这个递推,很多人就直接写了,有没有人讲讲啊 import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { int count = in.nextInt(); int sum = in.nextInt(); int[] array = new int[count+1]; for (int i = 1; i <= count; i++) array[i] = in.nextInt(); long[][] dp = new long[count + 1][sum + 1]; for (int i = 0; i <= count; i++) dp[i][0] = 1; for (int i = 1; i <= count; i++) { for (int j = 0; j <= sum; j++) { if (j >= array[i]) dp[i][j] = dp[i-1][j] + dp[i-1][j-array[i]]; else dp[i][j] = dp[i-1][j]; } } System.out.println(dp[count][sum]); } } }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); int n = cin.nextInt(); int m = cin.nextInt(); int arr[] = new int[n+1]; //代表你使用前i个数组组成j的最大组合数 long dp[][] = new long[n + 1][m + 1]; for (int i = 1; i <= n; i++) { arr[i] = cin.nextInt(); } for (int i = 0; i < m; i++) { dp[0][i] = 0; } //注意,你的dp[0][0]一定要是1,否则会出错 for (int i = 0; i < n; i++) { dp[i][0] = 1; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (arr[i] <= j) { dp[i][j] = dp[i - 1][j] + dp[i - 1][j - arr[i]]; } else { dp[i][j] = dp[i - 1][j]; } } } System.out.println(dp[n][m]); } }
//01背包问题的变形:根据数组前i-1个数相加和为j来决策加上第i个数是否符合条件, //状态转移方程为f[i][j] = f[i-1][j] + f[i-1][j-target] (j>=target) //其中f[i][j]表示数组前i个数中相加和为j的方案数 //f[i-1][j] 表示数组前i-1个数中相加和为j的方案数 //f[i-1][j-target]表示数组前i-1个数中相加和为j-target的方案数,要求j>=target, //否则令f[i-1][j-target]=0; // 以数组{3,2,10,5,5},target=15为例: //以下表格从下往上,从左到右反映了状态的转移过程,理解了这个表格的建立过程,也就理解了01背包 // // i a[i] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 // 4 5 0 1 1 0 3 0 2 2 0 4 0 2 2 0 4 // 3 5 0 1 1 0 2 0 1 1 0 2 0 1 1 0 2 // 2 10 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 // 1 2 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 // 0 3 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 import java.util.*; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); int target = in.nextInt(); int[] a= new int[n]; for(int i=0; i<n; ++i){ a[i] = in.nextInt(); } long res = dfs(a,target); System.out.println(res); } public static long dfs(int[] array, int target){ long [][] dp = new long[array.length][target+1]; //表示j-target为0时,方案数加1 for (int i=0;i<array.length; ++i){ dp[i][0] = 1; } for (int i=0; i<array.length; ++i){ for (int j=1; j<=target; ++j){ if (i == 0) { dp[i][j] = j-array[i] == 0 ? 1 : 0; }else { long temp = j - array[i] >= 0 ? dp[i-1][j - array[i]] : 0; dp[i][j] = dp[i - 1][j] + temp; } } } return dp[array.length-1][target]; } }
package LineCode.Recruit2017.滴滴出行; import java.util.Scanner; /** * 给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。 * 当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。 */ public class 数字和为sum的方法数 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { //输入 int n = sc.nextInt(); int sum = sc.nextInt(); int[] arrs = new int[n]; for (int i = 0; i < n; i++) { arrs[i] = sc.nextInt(); } //处理 long [] dp = new long[sum+1]; dp[0] = 1; for (int i = 0; i < n; i++) { for (int j = sum; j >= arrs[i] ; j--) dp[j] += dp[j-arrs[i]]; } //输出 System.out.println(dp[sum]); } } }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int sum = sc.nextInt(); int [] A = new int[n]; long [] f = new long[sum+1]; for(int i=0;i<n;i++){ A[i] = sc.nextInt(); } f[0] = 1; for (int i=0;i<n;i++) { for (int j=sum;j>=0;j--) { if(j>=A[i]) { f[j] += f[j-A[i]]; } } } System.out.println(f[sum]); } }