/sci/ - Science & Math » Thread #11085151

26KiB, 620x342, programming.jpg

View Same Google iqdb SauceNAO

Anonymous Wed 23 Oct 15:09:09 2019 No.11085151 View Reply Original Report

Quoted By: >>11085159 >>11085199 >>11086130 >>11086451 >>11086880 >>11086939 >>11087704 >>11087766 >>11089408

I've been given a problem:
You are given an array with N numbers. You have to say if there are K numbers which sum is X. Do you know how to solve it?

Anonymous

Anonymous Wed 23 Oct 2019 15:12:55 No.11085159 Report

Quoted By: >>11085169

>>11085151
>homework thread
Here's your hint, it's a commonly-assigned CS problem and it has a name

Anonymous

Anonymous Wed 23 Oct 2019 15:16:58 No.11085169 Report

Quoted By: >>11085196

>>11085159
I can't find it, please help

Anonymous

Anonymous Wed 23 Oct 2019 15:27:59 No.11085190 Report

Quoted By:

bump

Anonymous

Anonymous Wed 23 Oct 2019 15:29:55 No.11085196 Report

Quoted By:

>>11085169
Your homework assignment isn't to guess the name and look it up on wikipedia dumbass. Though feel free to try

Anonymous

Anonymous Wed 23 Oct 2019 15:31:52 No.11085199 Report

Quoted By: >>11085755

>>11085151
Here you go OP
https://en.wikipedia.org/wiki/Subset_sum_problem

Ignore the faggots. Knowledge is power!

Anonymous

Anonymous Wed 23 Oct 2019 18:46:02 No.11085755 Report

Quoted By: >>11085773 >>11085775

>>11085199
but these numbers don't have to be a subset

Anonymous

Anonymous Wed 23 Oct 2019 18:50:10 No.11085773 Report

Quoted By: >>11085786

>>11085755
what are you talking about

Anonymous

Anonymous Wed 23 Oct 2019 18:50:19 No.11085775 Report

Quoted By: >>11085786

>>11085755

what do you mean?

Anonymous

Anonymous Wed 23 Oct 2019 18:54:08 No.11085786 Report

Quoted By: >>11085794

>>11085773
>>11085775
the wikipedia says about problem when you are looking for subset which sum is equal to some number, I have set for example
S = {4, 5, 9, 12, 3, 2}
and I need 3 numbers which sum up to 16, so there are numbers: 4, 9, 3

Anonymous

Anonymous Wed 23 Oct 2019 18:56:20 No.11085794 Report

Quoted By: >>11085798

>>11085786
Are you retarded?

Anonymous

Anonymous Wed 23 Oct 2019 18:57:29 No.11085798 Report

Quoted By: >>11085812

>>11085794
why?

Anonymous

Anonymous Wed 23 Oct 2019 19:03:23 No.11085812 Report

Quoted By:

>>11085798
Define "subset" to me, please.

Anonymous

Anonymous Wed 23 Oct 2019 21:03:17 No.11086130 Report

Quoted By:

>>11085151
ill give you a hint: utilise running sums/prefix sums (whatever you want to call it). now do some thinking of your own :)

Anonymous

Anonymous Wed 23 Oct 2019 22:46:18 No.11086451 Report

Quoted By: >>11086790 >>11087994

>>11085151
>Do you know how to solve it?
The real question should be, do you know how to solve it EFFICIENTLY.

Anonymous

Anonymous Thu 24 Oct 2019 01:08:57 No.11086790 Report

Quoted By:

>>11086451
I would use dynamic programming, but there is probably a more clever approach which is actually slower in practice.

Anonymous

Anonymous Thu 24 Oct 2019 01:27:15 No.11086834 Report

Quoted By: >>11087750

1: take all subsets (2^n time)
2: sum them (const time)
3:compare every subset sum with K (n time)

its an NP-complete problem

Anonymous

Anonymous Thu 24 Oct 2019 01:46:38 No.11086880 Report

Quoted By: >>11086903

>>11085151
Not looking at shit, but here we go.
Let us assume that the array is a multi-set. This means that a number $i\in\mathbb{N}$ can appear in the set more than once. The approach to this is to use dynamic programming. We will define a bellman equation $\verb|OPT|$ to do this. What is the base cases of our operation? If we have an array with $n=0$ numbers, then there is no way that we can obtain the sum. Therefore, $\verb|OPT|([], k) = F$ . Likewise, if $n=1$ , we can only sum that number. Therefore, we should only accept if $A_n[n] = k[\math]Unfortunately, we cannot bound k. k can range from either positive to negative infinity. So, what are our cases for <script type="math/tex">\verb|OPT|$ ? It is either we include the first number, or do not. So, our bellman equation will be as follows.

$ \verb|OPT|(A_n, k) = \begin{cases} T&\text{if }\verb|OPT|(A_{n-1}, k - A_n[n]),\\ T&\text{if }\verb|OPT|(A_{n-1}, k),\\ T&\text{if }n=1\land A_n[n] = k,\\ F&\text{if }n=0,\\ F&\text{otherwise} \end{cases} $

The proof of the correctness and steps is left for the reader.

Anonymous

Anonymous Thu 24 Oct 2019 01:57:16 No.11086897 Report

Quoted By:

step 1:
spin up n! ec2 instances

you should be able to figure it out from there

Anonymous

Anonymous Thu 24 Oct 2019 02:01:50 No.11086903 Report

Quoted By: >>11088096

>>11086880
Errata: I fucked up the math tags. Unfortunately,we cannot bound $k$ . $k$ can range from either positive to negative infinity. So,what are our cases for $\verb|OPT|$ ?

Anonymous

Anonymous Thu 24 Oct 2019 02:17:39 No.11086939 Report

Quoted By:

>>11085151
Order array integers by size. Window array with progressively smaller sub arrays that do sums. Eventually you will get a window array of size 1 which finds all duplicate integers.

Anonymous

Anonymous Thu 24 Oct 2019 11:16:58 No.11087704 Report

Quoted By: >>11087939

>>11085151

let f(i, s, k) = 1 if it is possible to make sum s using a subset of size k from elements Ai, Ai+1, .... , An.
and 0 otherwise.

then, f(i, s, k) = f(i+1, s - Ai, k-1) [k > 0] OR f(i+1, s, k)

base case: f(n, s, k) = 1 if (k = 1 and s = An) or k = 0. 0 otherwise

keep a dp table to store results of visited states.
O(n*k*sum)

Anonymous

Anonymous Thu 24 Oct 2019 12:17:33 No.11087750 Report

Quoted By: >>11088560

>>11086834
no

Anonymous

Anonymous Thu 24 Oct 2019 12:34:15 No.11087766 Report

Quoted By:

>>11085151
have you ever been to the supermarket or does your handler do it for you

Anonymous

Anonymous Thu 24 Oct 2019 15:18:36 No.11087939 Report

Quoted By:

>>11087704
>base case
f(n, s, k) = 1 if (k = 1 and s = An) or "k = 0 and s = 0".
0 otherwise

Anonymous

Anonymous Thu 24 Oct 2019 15:54:36 No.11087994 Report

Quoted By: >>11087997

>>11086451
>he doesn't use assembly
lmao speedlet

Anonymous

Anonymous Thu 24 Oct 2019 15:58:07 No.11087997 Report

Quoted By:

>>11087994
>he doesn't use a quantum computer
lmao speedlet

Anonymous

Anonymous Thu 24 Oct 2019 16:41:18 No.11088096 Report

Quoted By:

>>11086903
you fucking suck at using math tags newfag

Anonymous

Anonymous Thu 24 Oct 2019 20:57:57 No.11088560 Report

Quoted By:

>>11087750
where was i wrong

Anonymous

Anonymous Fri 25 Oct 2019 03:59:31 No.11089408 Report

Quoted By:

>>11085151
did you have a midterm today OP?

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches