Additing numbers in list to equal x

use dynamic programming, this is a classical dynamic programming question

what language is this?

Are you implying a breadth first algorithm

lambda+ternary or stfu
double sum = yourList.Select(a => a ==x? sum +=x : sum);

Functional programming is always extra points. gj desuuu

what am I memoizing

>memoizing
bazozing

en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution

this is classical dynamic programming

int sum_equal_to_x(const int *numbers, const int x)
{
return x;
}

Great resource, thanks

"Given a set of integers, is there a non-empty subset whose sum is zero?" is a bit different from the ask since OP wants the smallest set possible.

Is the algo easily extendable to meet this need?

You are not dealing with your average coder anymore...

it's the same problem shifted by a constant. if you understand it you should be able to make such a small change. the more general version is the knapsack problem.

That is not what is being asked

Wrong
>Additing numbers in list to equal x
>to equal x
In other terms, y + z = x
You and are
thinking x + x = answer

def f(L, x):
s = sum(L)
s += x - s
return s

>the program has to give you the list of numbers that when being added equals 6
This is not what i asked for

I won't do your homework for you nigger. If you can't even do this stop studying and go clean shitters.

to equal x
AND
equal to x
Are two very different things.
The first is more complex than the second
The first is talked by:
And the second is:
???

i already am mate

just use the generating function

Attached: ss.png (149x50, 2K)

#include
#include
#include
// lol i misread it at first
static int increment_little_endian_bool_array(bool array[], int size) {
for (int i = 0; i < size; ++i) {
if (array[i]) {
array[i] = 0;
} else {
array[i] = 1;
return 1;
}
}
return 0;
}
static int popcnt_bool_array(const bool array[], int size) {
int n = 0;
for (int i = 0; i < size; ++i) if (array[i]) ++n;
return n;
}
static int sum_selection(const bool select[], const int from[], int size) {
int n = 0;
for (int i = 0; i < size; ++i) if (select[i]) n += from[i];
return n;
}
bool find_summands(const int array[], int output[], int size, int x) {
bool current[size], best[size];
memset(current, 0, sizeof(current));
memset(best, 0xff, sizeof(best));
memset(output, 0, size*sizeof(int));
int best_popcnt = size + 1;
do {
int n = sum_selection(current, array, size);
int pc = popcnt_bool_array(current, size);
if (n == x && pc < best_popcnt) {
memcpy(best, current, sizeof(best));
best_popcnt = pc;
}
} while (increment_little_endian_bool_array(current, size));
if (best_popcnt

i'm having a bit of trouble, i'm still a beginner. Bump so that the thread doesn't die before i'm finished

Look up Two Sum on leetcode, almost the same problem.

i'm trying to make it functional and with no side effects

def subsum(xs, n, m):
if (m==0) :
return True
if (n==0 and m!=0):
return False
if (xs[n-1] > m) :
return subsum(xs, n-1, m);
return subsum(xs, n-1, m) or subsum(xs, n-1, m-xs[n-1])

xs = [1,4,6,8,3,5,12]
n = len(xs)
m = 24

if (subsum(xs, n, m) == True):
print("found")
else :
print("not found")

It's a well known algorithm. See section 3.8, subset sum:
jeffe.cs.illinois.edu/teaching/algorithms/book/03-dynprog.pdf

dynamic programming took a while for me to understand too. I came across it while doing interview prep and honestly didn't understand how it was able to find the solution of some of the problems it works for.

Child-Jahy is cute

memoize with a hash map?

def addShit(list, sum):
dict = {}
for x, i in enumerate(sorted(list)):
if sum - x in dict:
return i, dict[sum-x]
else:
dict[x] = i

if this needs to support adding more than 2 then fuck yourself and do your hw

Python

usually you have a backtracking algorithm that you memoize. that chapter explains it well

I mean I understand it now. that was 7 years ago. I was just posting encouragement to user

Was reading xkcd, pic related is the best fit for this thread.

Attached: xkcd - 287 - NP-Complete - 1.png (640x414, 108K)

dpaste.de/4sQT
all the knowledge on programming i have atm are three lessons from MIT and a few chapters of land of lisp sorry :(