[编程题]小Q的歌单

题目

小Q有X首长度为A的不同的歌和Y首长度为B的不同的歌，现在小Q想用这些歌组成一个总长度正好为K的歌单，每首歌最多只能在歌单中出现一次，在不考虑歌单内歌曲的先后顺序的情况下，请问有多少种组成歌单的方法。
思路：

方案一：计算排列组合

for (int i = 0; i * A <= K&&i<=X; i++) {//长度为A的歌能出现的次数(次数肯定小于X)
    //i：A歌曲的数量
    if ((K-i*A)%B==0){
        int j=(K-i*A)/B;//B的数量
        if(j<=Y){//B出现的次数小于Y
            //不考虑A 和 B的先后顺序
            ans+=从X首A歌曲中取出i首的方案*从Y首B歌曲中取出j首的方案
        }
    }
}

在计算排列组合时，要防止溢出

/**
 * 计算C(n,m)
 *N*(N-1)*...*(N-M+2)(N-M+1)/(M*(M-1)*...*2*1)
 */
public static long help(int n,int m){
    long ans=1;
    int i=n-m+1;
    int j=1;
    while (i<=n){
        ans=ans*i/j;
        i++;
        j++;
    }
    return ans;
}

但是数据太大，还是会溢出

方案二：转换为0-1背包问题

有一个容量为K的背包，一共X+Y件物品，每件物品的体积为V[i]，求刚好装满背包的方案数

表示从前i件物品中选取若干件物品放入空间为j的背包，刚好装满的方案总数。

初始化：,放入背包容量为0的方案数是1，即什么都不放

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //每个测试用例的第一行包含一个整数，表示歌单的总长度K(1<=K<=1000)。
        int K = in.nextInt();
        //接下来的一行包含四个正整数，分别表示歌的第一种长度A(A<=10)和数量X(X<=100)
        int A = in.nextInt();
        int X = in.nextInt();
        // 以及歌的第二种长度B(B<=10)和数量Y(Y<=100)。保证A不等于B。
        int B = in.nextInt();
        int Y = in.nextInt();
        int[] V = new int[Y + X + 1];//将长度分别放到1-->X+Y
        Arrays.fill(V, 1, X + 1, A);
        Arrays.fill(V, X + 1, X + Y + 1, B);
        int[][] F = new int[X + Y+1][K + 1];
        F[0][0] = 1;//初始化F[0][0]
        for (int i = 1; i <= X + Y; i++) {
            for (int j = 0; j <= K; j++) {//体积从0到K
                if (j < V[i]) {
                    F[i][j]=F[i-1][j]%1000000007;
                }else{
                    F[i][j]=(F[i-1][j]+F[i-1][j-V[i]])%1000000007;
                }
            }
        }
        System.out.println(F[X+Y][K]);
    }
}

方案三：进行空间优化

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //每个测试用例的第一行包含一个整数，表示歌单的总长度K(1<=K<=1000)。
        int K = in.nextInt();
        //接下来的一行包含四个正整数，分别表示歌的第一种长度A(A<=10)和数量X(X<=100)
        int A = in.nextInt();
        int X = in.nextInt();
        // 以及歌的第二种长度B(B<=10)和数量Y(Y<=100)。保证A不等于B。
        int B = in.nextInt();
        int Y = in.nextInt();
        int[] V = new int[Y + X + 1];//将长度分别放到1-->X+Y
        Arrays.fill(V, 1, X + 1, A);
        Arrays.fill(V, X + 1, X + Y + 1, B);
        int[] F = new int[K + 1];
        F[0] = 1;//初始化
        //保证F[j]在更新之前使用
        for (int i = 1; i <= X + Y; i++) {
            for (int j = K; j >= 0; j--) {//体积从0到K
                if (j < V[i]) {
                    F[j]=F[j];
                }else{
                    F[j]=(F[j]+F[j-V[i]])%1000000007;
                }
            }
        }
        System.out.println(F[K]);
    }
}