A brute-force optimization problem

Правка en2, от jophyyjh, 2021-03-15 15:37:01

Hi guys, I'm quite new to programming. May I ask how the following problem could be solved?

The following is a problem I saw in a coding competition:

Problem Statement...

Given 2 positive integers N and M. Imagine that a stone manufacturer can make M different kinds of different stones, each with a positive integer weight. ("different" here means "with different weights") If we already know what these stones are, we can always find the largest positive integer K such that any weight between 1 and K (_inclusive_), we can form that weight with at most N stones (by selecting at most N stones so that the sum of these stones is that weight). We also know that each type of stones would have a sufficient amount of supplies. So when you are selecting those "at most N stones", you can choose whatever stones from that M types as long as the total number doesn't exceed N. Now, given N and M, your task is to find out (and output) the maximum possible value of K when you select those M types of stones optimally.

What I've tried

I've thought of dynamic programming, but this problem just seems too complicated. After a while of thinking without much results, I came to a thought that the intended solution is with some complete search or brute force method. But I haven't figured out how. Also, the problem constraints state that 1 <= N <= 8 and 1 <= M <= 6.

Test Cases (Just for Reference)

N = 2, M = 2 => 4

N = 3, M = 2 => 7

N = 5, M = 4 => 71

Thx a lot guys!!! I kindly appreciate any kind of help.

Теги brute-force, complete-search, optimization

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский jophyyjh 2021-03-15 15:37:01 4
en1 Английский jophyyjh 2021-03-15 15:35:48 1639 Initial revision (published)