Java实现用指定整数凑出用户输入数值的贪心算法问题

Hey there! Since you're new to Java and looking to implement a greedy algorithm for your denomination combination problem, let's walk through a complete solution that fits your needs.

First, let's recap your requirements: you have the values 2, 7, 23, 52, 113, want to start from the largest and accumulate to match the user's input (like 1000), and you already have a partial code snippet.

Approach #

The greedy approach here works best when we process denominations from largest to smallest. For each input number:

1. Start with the biggest value (113) and calculate how many times it fits into the remaining target number.
2. Subtract the total value of those counts from the remaining number.
3. Move to the next smaller denomination and repeat until we've checked all values.
4. If we end up with a remaining value of 0, we've found a valid combination; otherwise, the number can't be formed exactly with the given values.

Complete Java Code #

Here's the full code that builds on your existing snippet, with explanations embedded:

import java.util.Scanner;

public class GreedyCombinationGenerator {
    public static void main(String[] args) {
        // Define denominations in DESCENDING order (critical for greedy!)
        int[] denominations = {113, 52, 23, 7, 2};
        // Optional: Labels to make output clearer
        String[] denomNames = {"113", "52", "23", "7", "2"};

        Scanner sc = new Scanner(System.in);
        System.out.println("Enter a number to form (enter negative to exit): ");

        while (true) {
            int target = sc.nextInt();

            // Exit loop if user enters a negative number
            if (target < 0) {
                System.out.println("Thanks for using the program!");
                break;
            }

            int remaining = target;
            StringBuilder combination = new StringBuilder();

            for (int i = 0; i < denominations.length; i++) {
                int currentDenom = denominations[i];
                int count = remaining / currentDenom;

                if (count > 0) {
                    // Add to result string with proper formatting
                    if (combination.length() > 0) {
                        combination.append(" + ");
                    }
                    combination.append(count).append("×").append(denomNames[i]);
                    // Update remaining value after using these denominations
                    remaining = remaining % currentDenom;
                }
            }

            // Check if we successfully formed the target number
            if (remaining == 0) {
                System.out.printf("Combination for %d: %s%n", target, combination);
            } else {
                System.out.printf("Cannot form %d exactly. Remaining value: %d%n", target, remaining);
            }

            System.out.println("\nEnter another number (or negative to exit): ");
        }

        sc.close();
    }
}

Key Details Explained #

• Denomination Order: By sorting values from largest to smallest, we ensure we always pick the biggest possible value first—this is the core of the greedy strategy.
• Exit Condition: Added a check for negative inputs so the program doesn't run infinitely (your original snippet was missing a way to exit the loop).
• StringBuilder: Used to efficiently build the output string without messy concatenation, adding "+" only when there's already a part of the combination.
• Integer Division & Modulus:
  • remaining / currentDenom gives how many times the denomination fits into the remaining value (e.g., 1000 / 113 = 8).
  • remaining % currentDenom gives the leftover value after using those denominations (1000 % 113 = 96).

Example Output #

When you input 1000, the program will output:

Combination for 1000: 8×113 + 1×52 + 1×23 + 3×7

Which is the correct greedy breakdown (8113=904, 152=52, 123=23, 37=21; sum is 904+52+23+21=1000).

Note on Edge Cases #

• Numbers like 1 can't be formed (since the smallest denomination is 2), so the program will inform you of the remaining value.
• Negative inputs trigger the exit, making the user experience smoother.

内容的提问来源于stack exchange，提问作者Frank Grossmann