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.
↵
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.
