硬币找零问题的变种

区别在哪？

这里不需要等于amount，可以>=amount

动态规划解：

//不对
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
	// write your code here

        Scanner scanner=new Scanner(System.in);
        while (scanner.hasNext())
        {
            int n=scanner.nextInt();
            int m=scanner.nextInt();

            int a[]=new int[n+1];
            int b[]=new int[n+1];
            for(int i=0;i<n;i++)
            {
                a[i+1]=scanner.nextInt();
            }
            for(int i=0;i<n;i++)
            {
                b[i+1]=scanner.nextInt();
            }

            int f[][]=new int[n+1][m+1];




            for(int i=1;i<=m;i++)
            {
                if(a[1]>i)
                {
                    f[1][i]=Integer.MAX_VALUE;
                }
                else
                {
                    if(i%a[1]!=0)
                    {
                        f[1][i]=i/a[1]+1;//和硬币找零不相同
                    }
                    else
                    {
                        f[1][i]=i/a[1];
                    }

                }
            }

            for(int i=0;i<=n;i++)
            {
                f[i][0]=0;
            }

            for(int i=2;i<=n;i++)//不要从f[0][m]开始算 f[1][m]=min{f[0][m], ,,,,}不成立
            {
                for(int j=0;j<=m;j++)
                {
                    int min=Integer.MAX_VALUE;
                    for(int q=0;q<=b[i]&&q<=j/a[i];q++)
                    {

                        //System.out.println(i+"***"+q+":"+(f[i-1][j-q*a[i]]+q));
                        if(f[i-1][j-q*a[i]]!=Integer.MAX_VALUE&&min>f[i-1][j-q*a[i]]+q)
                        {
                            min=f[i-1][j-q*a[i]]+q;

                        }

                    }
                    f[i][j]=min;

                }



            }

            System.out.println(f[n][m]);
        }
    }
}
//但是m这里太大，空间复杂度太高,利用贪心。

//每次选择最大的，就可以直接找到最小钱币数大于amount

//题目延伸

//求集合中大于某个阈值的最小值

硬币找零问题的变种

相关推荐