竞赛讨论区 > 背包问题:求有多少种组合加起来是m
头像
可菲
发布于 2020-08-07 17:36
+ 关注

背包问题:求有多少种组合加起来是m

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();//表示数据组数
        int ans=0;
        for(int i=0;i<T;i++){
            int n = sc.nextInt();//n种不同面额的货币
            int[] a = new int[n];//货币面额数组
            for(int j=0;j<n;j++){
                a[j] = sc.nextInt();
            }
            Arrays.sort(a);
            //将面额数组中能被其他面额表示出来的删掉,剩下的个数即为答案
            //背包问题:a[1..i-1]能否拼出a[i]
            int count = huoBiXiTongII(n,a[n-1],a);
            System.out.println(count);
        }
    }
    public static int huoBiXiTongII(int n,int m,int[] a){
        //背包问题:n个物品,m容量,ai可用多次,求有多少种组合加起来是m
        //f[i]表示有多少种组合能拼出容量i
        int[] f = new int[m+1];
        f[0]=1;//有1种组合能拼出0(什么都不选),f[1]=...=f[m]=0
        int i,j;
        for(i=1;i<=m;++i){
            for(j=0;j<n;j++){
                //如果i<a[j],则对应的f[i-a[j]]不加入f[i]
                if(i>=a[j]){
                    f[i] += f[i-a[j]];
                }
            }
        }
        int count = 0;
        for(i=0;i<a.length;i++){
            //面额只有一种组成方式,即不能被其他面额表示出
            if(f[a[i]] == 1){
                ++count;
            }
        }
        return count;
    }
}

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐