最小瓶数 Java 代码中的意外结果

Question

以下 Java 代码计算存储给定体积液体所需的最少瓶子数。瓶子的存储容量是 {1,5,7,10}。它适用于较小的值（如 4 位数字），但适用于较大的值，如 99999（堆栈溢出错误）、1000000（错误答案）及以上。代码有什么问题？预计会更正代码以及故障描述。

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

public class Minimise
{
  static final int INF = 1000000000;
  static int dp[]=new int[1000010];

  public static void main(String[] args)
   {
    Scanner s = new Scanner(System.in);

    System.out.println("enter the volume");
    int size = s.nextInt();

    Arrays.fill(dp, 0, 100000, -1);

    System.out.println("minimum number of bottles needed:\n"+findmin(size));
   }

  static int findmin(int size)
   {
    if(size<0)
        return INF;
    else if(size==0)
        return 0;        

    if( dp[size] != -1 )
        return dp[size];        
    else
    {
        dp[size] = min( findmin(size-10)+1, findmin(size-7)+1, findmin(size-5)+1, findmin(size-1)+1 );            
        return dp[size];
    }
 }

  static int min(int a,int b,int c,int d)
  {
    int arr[] = new int[4];
    arr[0] = a;
    arr[1] = b;
    arr[2] = c;
    arr[3] = d;
    Arrays.sort(arr);
    return arr[0];
   }
  }

Answer 1

尝试

Arrays.fill(dp, 0, dp.length, -1)

您要离开 dp[100000] >= 0。

对于堆栈溢出错误，使用 Moar Stack：

java -Xss4m Minimise

最小瓶数 Java 代码中的意外结果

Unexpected results in minimum bottles Java code

java

algorithm

recursion

memoization