小米大礼包

[编程题]小米大礼包

热度指数：4670 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

小米之家是成人糖果店。里面有很多便宜，好用，好玩的产品。中秋节快到了，小米之家想给米粉们准备一些固定金额大礼包。对于给定的一个金额，需要判断能不能用不同种产品（一种产品在礼包最多出现一次）组合出来这个金额。聪明的你来帮帮米家的小伙伴吧。

输入描述:

输入 N （N 是正整数， N  <= 200）
输入 N 个价格p（正整数, p <= 10000）用单空格分割
输入金额 M（M是正整数，M <= 100000 ）

输出描述:

能组合出来输出 1
否则输出 0

示例1

输入

6
99 199 1999 10000 39 1499
10238

输出

算法知识视频讲解

Java

崔乐颖

求讲解

发表于 2019-09-05 20:40:30 回复(0)

Java

不忘初心ff

import java.util.*;
public clas***ain{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int n=sc.nextInt();
            int[] arr=new int[n];
            for(int i=0;i<n;i++){
                arr[i]=sc.nextInt();
            }
            int sum=sc.nextInt();
            if(getResult(arr,sum)){
                System.out.println(1);
            }else{
                System.out.println(0);
            }
        }
    }
    //dp[i][j]表示arr的前i个数能否得到和j，每一个数都可以取或者不取
    public static boolean getResult(int[] arr,int sum){
        int n=arr.length;
        boolean[][] dp=new boolean[n+1][sum+1];
        dp[0][0]=true;
        for(int i=1;i<=n;i++){
            dp[i][0]=true;
        }
        for(int j=1;j<=sum;j++){
            dp[0][j]=false;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=sum;j++){
                dp[i][j]=dp[i-1][j];
                if(j>=arr[i-1]){
                    dp[i][j]=dp[i][j]||dp[i-1][j-arr[i-1]];
                }
            }
        }
        return dp[n][sum];
    }
}

发表于 2019-05-17 09:43:01 回复(0)