Giá trị tem bưu chính tối đa trên một phong bì

Question

Vấn đề tem bưu chính là một câu đố toán học hỏi giá trị bưu chính nhỏ nhất không thể được đặt trên phong bì là bao nhiêu chỉ có các giá trị khuôn mặt được chỉ định nhất định. Ví dụ: giả sử phong bì chỉ có thể chứa ba tem và giá trị tem sẵn có là 1 xu, 2 xu, 5 xu và 20 xu. Sau đó, giải pháp là 13 xu; vì bất kỳ giá trị nhỏ hơn nào có thể đạt được với tối đa ba tem (ví dụ: 4 = 2 + 2, 8 = 5 + 2 + 1, v.v.), nhưng để có được 13 xu thì phải sử dụng ít nhất bốn tem.

Có thuật toán nào cho số lượng tem tối đa được phép và giá trị khuôn mặt của tem không, có thể tìm thấy bưu phí nhỏ nhất không thể đặt trên phong bì?

Một ví dụ khác:
Tối đa 5 tem thể được sử dụng
Quý: 1, 4, 12, 21
Giá trị nhỏ nhất mà không thể đạt được 72. Giá trị 1-71 có thể được tạo ra với một sự kết hợp nhất định .

Cuối cùng tôi có thể sẽ sử dụng Java để mã hóa điều này.

Answer 1

Có, có một thuật toán như vậy. Naively: bắt đầu bằng 1, hãy thử mọi kết hợp tem có thể cho đến khi chúng tôi tìm thấy kết hợp mang lại tổng cộng 1, sau đó thử cho 2, v.v. Thuật toán của bạn kết thúc khi nó tìm thấy một số sao cho không có sự kết hợp nào của tem thêm vào số đó.

Tuy có thể chậm, cho các vấn đề đủ nhỏ (nói 100 tem, 10 vị trí), bạn có thể giải quyết việc này trong một khoảng "hợp lý" của thời gian ...

Nhưng, đối với những vấn đề lớn, những nơi chúng tôi có nhiều tem có sẵn (nói 1000s) và nhiều vị trí có thể (nói 1000s), thuật toán này có thể mất một khoảng thời gian khó xử. Đó là, đối với những vấn đề rất lớn, thời gian để giải quyết vấn đề bằng cách sử dụng phương pháp này có thể nói, tuổi thọ của vũ trụ, và do đó nó không thực sự hữu ích cho bạn.

Nếu bạn có vấn đề thực sự lớn, bạn cần phải tìm cách để tăng tốc độ tìm kiếm của bạn, các tăng tốc này được gọi là heuristics. Bạn không thể đánh bại vấn đề, nhưng bạn có thể giải quyết vấn đề nhanh hơn cách tiếp cận ngây thơ bằng cách áp dụng một số kiến ​​thức về miền. Một cách đơn giản để cải thiện cách tiếp cận ngây thơ này có thể là bất kỳ lúc nào bạn thử kết hợp tem không bằng số bạn đang tìm kiếm, bạn xóa kết hợp đó khỏi tập hợp có thể để thử bất kỳ số nào trong tương lai, và đánh dấu số tương lai đó là không có sẵn. Nói cách khác: giữ một danh sách các số bạn đã tìm thấy và các kết hợp đã đưa bạn đến đó, sau đó không tìm kiếm những con số đó hoặc kết hợp của chúng một lần nữa.

Answer 2

Thay vì tính toán toàn bộ số tiền của tất cả các kết hợp tem có thể (có thể bằng đệ quy), hãy xem xét tất cả số tiền có thể và tìm ra số tem nhỏ nhất để tạo ra mỗi tổng. Có vô số các kết hợp tem, nhưng có rất ít khoản tiền khác nhau.

Trong ví dụ bạn đưa ra nhận xét, 10 tem phù hợp trên phong bì và không có tem có giá trị lớn hơn 100. Có n^10 kết hợp tem, trong đó n là số mệnh giá tem sẵn có. Nhưng số tiền lớn nhất có thể là 10 tem chỉ là 1000. Tạo một mảng lên tới 1001, và cố gắng nghĩ ra một cách hiệu quả để làm việc, cho tất cả các giá trị đó lại với nhau, số tem ít nhất cần thiết để tạo ra mỗi tem.Câu trả lời của bạn sau đó là chỉ số ít nhất yêu cầu tem 11 (hoặc nhiều hơn) và bạn cũng có thể giới hạn số lượng tem ở mức 11.

"Hiệu quả" trong trường hợp này về cơ bản có nghĩa là "tránh lặp lại bất kỳ tác phẩm nào bạn không phải làm". Vì vậy, bạn sẽ muốn sử dụng lại kết quả trung gian càng nhiều càng tốt.

Nếu đó không đủ gợi ý thì (a) Tôi sai về cách tiếp cận (trong trường hợp này, tôi chưa thực sự giải quyết được vấn đề trước khi trả lời) hoặc (b) cập nhật để nói cách xa bạn đã có những dòng đó.

Answer 3

Dưới đây là một mẹo khác: Mỗi bộ tem có thể thêm vào một số số nhất định có thể được tạo thành bằng cách thêm 1 tem vào một tập hợp tem có kích thước tối thiểu có thể thêm tối đa số đó.

Ví dụ: giả sử chúng tôi có tem 1, 2, 7, 12 và 50 và giới hạn 5 tem và chúng tôi muốn tìm hiểu xem liệu 82 có thể được biểu diễn hay không. Để nhận được rằng 82, bạn phải thêm một trong hai:

• Một từ 1 tới một bộ tem thêm lên đến 82-1 = 81, hoặc
• Một 2 đến một bộ tem thêm lên đến 82-2 = 80, hoặc
• một 7 đến một bộ tem thêm lên đến 82-7 = 75, hoặc
• một 12 đến một bộ tem thêm lên đến 82-12 = 70, hoặc
• một 50 đến một bộ tem thêm 82-50 = 32.

Đó là những cách duy nhất có thể tạo thành 82. Trong số tất cả 5 khả năng đó, một (hoặc có thể nhiều hơn một) sẽ có số lượng tem tối thiểu. Nếu số tối thiểu đó là> 5, thì 82 không thể được đại diện bằng tem.

Cũng lưu ý rằng nếu một số có thể được biểu diễn, bạn cần phải ghi lại số lượng tem tối thiểu cần thiết để tính toán cho số cao hơn có thể sử dụng số đó.

Điều này, cộng với Steve Jessop's answer, hy vọng sẽ giúp bạn suy nghĩ đúng đắn về giải pháp lập trình động ... Nếu bạn vẫn bối rối, hãy cho tôi biết.

Answer 4

Có thể hơi vô ích khi chỉ đưa ra "gợi ý" về giải pháp DP khi có suy đoán rằng thậm chí tồn tại. Vì vậy, đây là Runnable Perl code thực hiện các thuật toán DP thực tế:

#!/usr/bin/perl 
my ($n, @stamps) = @ARGV; 
my @_solved;  # Will grow as necessary 

# How many stamps are needed to represent a value of $v cents? 
sub solve($) { 
    my ($v) = @_; 
    my $min = $n + 1; 

    return 0 if $v == 0; 

    foreach (@stamps) { 
     if ($v >= $_) { 
      my $try = $_solved[$v - $_] + 1; 
      $min = $try if $try < $min; 
     } 
    } 

    $_solved[$v] = $min; 
    return $min; 
} 

my $max = (sort { $a <=> $b } @stamps)[-1]; 

# Main loop 
for (my $i = 0; $i <= $max * $n; ++$i) { 
    my $ans = solve($i); 
    if ($ans > $n) { 
     print "$i cannot be represented with <= $n stamps of values " . join(", ", @stamps) . ".\n"; 
     last; 
    } 
} 

Thông thường solve() sẽ yêu cầu một cuộc gọi đệ quy, nhưng bởi vì chúng tôi luôn cố gắng giá trị theo thứ tự 0, 1, 2, 3 ..., chúng tôi chỉ có thể sử dụng mảng @_solved trực tiếp để nhận câu trả lời cho các kích thước vấn đề nhỏ hơn.

Điều này cần 93ms trên máy tính của tôi để giải quyết trường hợp kích thước tem 1, 4, 12, 21 và kích thước phong bì 1000. (Câu trả lời là 20967.) Ngôn ngữ được biên dịch sẽ còn nhanh hơn nữa.

Answer 5

 import java.util.ArrayList; 
     import java.util.List; 
     /** 
     * 
     * @author Anandh 
     * 
     */ 
     public class MinimumStamp { 

      /** 
      * @param args 
      */ 
      public static void main(String[] args) { 
       // TODO Auto-generated method stub 
       int stamps[]={90,30,24,15,12,10,5,3,2,1}; 
       int stampAmount = 70; 
       List<Integer> stampList = minimumStamp(stamps, stampAmount); 
       System.out.println("Minimum no.of stamps required-->"+stampList.size());  
       System.out.println("Stamp List-->"+minimumStamp(stamps, stampAmount)); 
      } 

      public static List<Integer> minimumStamp(int[] stamps, int totalStampAmount){ 
       List<Integer> stampList = new ArrayList<Integer>(); 
       int sumOfStamps = 0; 
       int remainingStampAmount = 0; 
       for (int currentStampAmount : stamps) { 
        remainingStampAmount = totalStampAmount-sumOfStamps; 
        if(remainingStampAmount%currentStampAmount == 0){ 
         int howMany = remainingStampAmount/currentStampAmount; 
         while(howMany>0){ 
          stampList.add(currentStampAmount); 
          howMany--; 
         } 
         break; 
        }else if(totalStampAmount == (sumOfStamps+currentStampAmount)){ 
         stampList.add(currentStampAmount); 
         break; 
        }else if(totalStampAmount > (sumOfStamps+currentStampAmount)){ 
         int howMany = remainingStampAmount/currentStampAmount; 
         if(howMany>0){ 
          while(howMany>0){ 
           stampList.add(currentStampAmount); 
           sumOfStamps += currentStampAmount; 
           howMany--; 
          } 
         }else{ 
          stampList.add(currentStampAmount); 
          sumOfStamps += currentStampAmount; 
         } 
        } 
       } 
       return stampList; 
      } 
     }