Click here to Skip to main content
15,169,069 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
See more:
You are given N numbers which you must divide into two sets. Find me
how many ways can the integers be divided into two sets so that each set
to have a total sum greater than or equal to an integer S. In each set can
there must be a different number of integers.
Input data
• The first line contains two integers separated by a space: The N where
denotes the number of integers and S.
• The second line contains N integers.
Input data
An integer, in how many possible ways can the two be separated
totals. The number should appear modulo 109 + 7.
Input Example
5 12
3 4 5 6 7
Exit Example
4
Illustration
The two sets that can be created in each case are the following:
1. [3, 4, 5] - [6, 7]
2. [3, 4, 6] - [5, 7]
3. [6, 7] - [3, 4, 5]
4. [5, 7] - [3, 4, 6]


What I have tried:

PLEASE HELP ME
Is there a dynamic programming approach to this problem?
Posted
Updated 7-Mar-21 1:19am

First of all, this obviously comes from a challenge site, it is a good idea to give a link to original page because exact wording matters.
Quote:
Is there a dynamic programming approach to this problem?

The answer is rather simple, Dynamic Programming is an optimization, it is about avoiding doing same calculations again and again.

So the method is rather simple :
1) Build a solution for the problem, as simple as possible.
2) Make sure problem is solve, if not refine your solution until it works.
3) Analyze how your program solves the problem, if you spot that your code is recalculating the same thing again and again, then dynamic programming can apply.
   
We are more than willing to help those that are stuck: but that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^] and think about how you would do it manually.
   
Comments
Cplusplus Robotics 7-Mar-21 6:20am
   
IT IS NOT FOR HOMEWORK, F*** MY LIFE. I MADE THIS PROBLEM AND I NEED A SOLUTION
OriginalGriff 7-Mar-21 7:05am
   
If it's posted by someone new to the site, reads exactly like a homework question, and shows no sign whatsoever of nobody even trying to actually solve it what would you assume it was?
Do you think "real world" tasks are phrased like that?

And do you think SHOUTING and swearing at people you want help from is really a good idea? And that's ignoring the multiple exclamation marks which are (according to Sir pTerry) "a sure sign of a diseased mind".

So, get off your high horse, get on your keyboard and try it. Follow the link I gave you and read what it says, then give it a try - instead of expecting others to do everything for you.
Your attitude so far is not going to get you far in the real world.
jeron1 7-Mar-21 11:31am
   
"F*** MY LIFE."
An optimist I see LOL!
MY GOD, WHY YOU THINK IT IS FOR HOMEWORK? F..M...L. I MADE THIS PROBLEM F*** AND I NEED A SOLUTION. JUST TELL ME HOW TO DO IT AND NOT THE IMPLEMENTATION F*** AGAIN. THE INTERNET MAN CAUSED ME HEADACHES!!!
   
Comments
jeron1 7-Mar-21 17:58pm
   
If you made the problem, then you make it too difficult. Make a simpler problem, and solve that, then slowly add to the level of difficulty as you LEARN the c++ language. If you have specific question, the good folks here are usually more than willing to assist.
P.S. some times tin foil helps fight the internet man. ;)

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900