This is the brainlet cutoff. You can't call yourself a programmer if you can't solve this

Why is there one 1kg block that's worth $2 and one 1kg block that's only worth $1? It's not like there's a money limit.

aww, widdle OP just started his algorithms course

Made of different materials?

I'm actually learning how to program, so let me give this a try:
Make a function with an argument: the space available. For every element remaining, check if it fits. If it doesn't, it gets eliminated. Then, check the weight to value ratio. The one with the best ratio is added to the bag array and eliminated from the options.
Then the function is called again with the value of the space available (total space - space used by elements already inside). Loop until complete.

Material has no impact. Also after further examination, there's a 2KG block worth $2 and a 1KG block worth $2. So right away we have 2 blocks that no one would even think of using. What kind of shitty problem is this?

greedy fit sorted by value per weight

>Material has no impact

1kg of feathers
1kg of gold

I think material has some impact on value

That image flares my autism

that's right
it's a kilogram of steel
youtube.com/watch?v=r1gyD7fCimA

Simple, shove all of it in there and if the wearer complains, insult them for being too poor to get a bigger backpack.

Knapsack problem for 500 James.

>sort by weight to value ratio
>put it in

wow that was hard

This problem has no feathers or gold user. They're just blocks with values, mass, and different color.

Thats the correct output, the trick is making a program that can do that

I'll try. There will be syntax issues because I'm really new to this. Brb.

printf("blue, grey, orange, yellow");

How about using a montecarlo approach?

I suppose you could brute force it, but that's not elegant..

What if you sort by highest value per kg then try to brute force it using the highest value per kg and then less and less value per kg?

This is exactly what I was thinking.

returns the highest total value, could be modified to return the contents

public int discreteKnapsack(int[] weights, int[] values, int capacity){

int n = weights.length;
int c = capacity;

Integer[][] table = new Integer[n][c];
int result = knap(n-1, c-1, weights, values, table);
return result;
}

public int knap(int n, int c, int[] weights, int[] values, Integer[][] table){
if(n < 0 || c < 0) return 0;
if(table[n][c] != null) return table[n][c]; //use memoized value
int result;
if(weights[n] > c+1) result = knap(n-1, c, weights, values, table);
else{
int temp1 = knap(n-1, c, weights, values, table);
int temp2 = values[n] + knap(n-1, c-weights[n], weights, values, table);
result = Math.max(temp1, temp2);
}
table[n][c] = result;
return result;
}

I'm this user have to leave home, I will continue later, I only did this. I am unsure if I can loop through an object or that's only arrays.

Attached: Screenshot_2018-09-23_18-22-56.png (561x410, 34K)

this is day one algs + data structures

fifteen grey boxes

shut the fuck up

sort items by value/weight
for each item in sorted list, insert to container if it fits

Wouldn't work with arbitrary input. For example, if the items were:

$6 3kg
$29 15kg
$1 1kg

Then the best solution would be to leave the first item in favor of the second.

>Subset_sum_problem

The problem of the subset sum is introduced with negative numbers.
If you have only positive numbers, you can use the order to your advantage. The value to sort is VALUE/WEIGHT.
1) take item with highest value density left.
2) fit in as much as you can (integer division) in the remaining weight difference.
start over.
If you have to skip items because there is not enough space left, you might have to reduce the former values, if their weight is higher than the next. This is true in particular for value densities close to each other. You might have to work out a formula how to calculate that.

If you can pick only one of each item, it is pretty much the same.

You meant 3 yellow and 3 grey?

I solved this on a whiteboard some months ago (that version of the problems had cakes)

quite basic stuff actually
I agree, everybody should be able to solve this

Attached: cakeproblem.jpg (2481x1481, 186K)

You will use a branch and bound approach for a knapsack problem.

Do you own homework.

Lmao get back to me when you solve traveling salesman in O(log n)

Attached: 7774C2F8-3B9F-4F5E-B84D-290363A85F36.png (800x800, 636K)

3 yellow, 1 gray, and 1 orange = $33.

JavaScript rocks!

>the knapsack problem
>is an integer program with a single constraint and binary decision variables, the objective function is to maximize the value inside the pack
brings back memories, thanks for sharing this user.

Does that mean you’ve been taught this specific algorithm before?

Calculate the $/kg for each box. Then fill as many as possible of the best one and then fill out with the others in falling order.
Am i missing something?

three boxes
gg gs ss
you pick g
chance for another g
go

I've solved it people. you don't have to keep trying

i took it in the course of Operations Research, the knapsack problem is a very famous one. We were also taught network flow problems, salesman problem, etc. It was quite the pleb filter since you had to convert case studies into a mathematical program. That was a very good course to be honest fampai.

it's not an algorithm
it's a problem with no "solution"
en.wikipedia.org/wiki/Knapsack_problem

>The problem often arises in resource allocation where there are financial constraints and is studied in fields such as combinatorics, computer science, complexity theory, cryptography, applied mathematics, and daily fantasy sports.
>daily fantasy sports

Attached: 319C808A-E75E-475E-85B6-BB1B97D9EFC2.jpg (225x225, 22K)

$36
3 of the $10 4kg blocks and 3 of the $2 1kg blocks

>javascript
Not gonna make it.

You don't get multiple bricks

Brainlet test failed

Those values actually allow for a trivial solution.
Note that yellow has the best value/weight ration with 2.5 $/kg, and silver the second best with 2 $/kg.
Just fill you bag with as much yellow until no more will fit, giving you 30$ and 12kg, then fill the rest with silver, adding 6$ and 3kg, adding up to 36$

$10, 5
$5, 3
$6, 4
Max weight: 7

Don't call us, we'll call you.

This is an approximate solution that doesn't give the absolute best result for some input values. But it's a pretty good solution. I wouldn't bother to implement anything more effective

the problem doesn't specify it you monkey.

This is taught in the 2nd or 3rd to last semester of getting your bachelor's in CS. It's called the Napsack Problem and it's gone over and practiced for 1 to 2 weeks.

Also, can there be duplicate items? It's a different problem if not, but much simpler. (duplicates require a matrix, unique only requires an array)

not him but what about running several iterations of it but skip an item each iteration and then finding the one with the highest sum?

I had no formal education in coding, but it sounds simple enough.

Divide the weight by the dollars. So you know how much 1 dollar weighs for each item.
Then input the ones in order of the least to the most weight per dollar.

>you are a brainlet if you haven't been taught a certain algorithm
Okay.

This is an NP-complete problem. Either brute force over every permutation and pick the optimal result, or go with greedy approximation algorithm, then kys.

Everything but the big useless 12kg box

Attached: 1537291622864.png (1512x1000, 264K)

Attached: don draper.jpg (855x575, 63K)

>that's᠌ ᠌t᠌h᠌e᠌ ᠌c᠌o᠌r᠌re᠌c᠌t᠌ ᠌o᠌u᠌t᠌p᠌ut᠌
n᠌o᠌p᠌e᠌

36 { yellow: 3, grey: 3 }

I am not going to show my code, because its proprietary.

Fuck you OP I'll just use BOGO sort to find the solution.

You never said it had to be optimized.

That's only a value of $30.
3 yellow boxes and 3 grey boxes have a value of $36

Use combinatorics to test every possible solution and use the best one.

Attached: 1537581283673.png (1268x1000, 929K)

/thread

that wont work

suppose we had a 10kg bag
and we have three items:
>$8 / 6kg
>$5 / 5kg
>$5 / 5kg

Your method would put the 6kg item in the bag and then stop, whereas the optimal solution is both 5kg items

Un ironically good approach
Worst case 5! = 120 possible cases.
But begin intro to dynamic programming problems

>4+4+4 > 15
What are you smoking?

>4᠌ ᠌k᠌g᠌
>᠌3᠌ ᠌*᠌ ᠌4᠌ ᠌=᠌=᠌ ᠌ ᠌ 12
>12᠌ ᠌

>Posts the knapsack problem
>everyone trying to find the correct DP solution
>even the good solutions take years on non-trivial problems just for "muh guarantee of correctness"

>doesn't realize this is a classic place to use a genetic algorithm which can give you an almost global maximum in seconds / global maximum it in minutes instead

Oh well, I guess that's why I'm at google and you're not :^)

If you have a 15 kg bag, one 9 kg $9 block, and two 7 kg $6 blocks, then sorting by weight/value gives you $9, but you can get $12

It never says you have a limited amount of the items, just limited weight capacity.So I put in 3 yellow boxes (4k and 10 bucks each) then I put in 3 of the grey boxes (1 kg at 2 bucks each).

>genetic algorithm meme
I guess that's why you're a janitor at google.

Baby's first stochastic algorithm.

>genetic algorithm
I was just about to code one.

class KnapSack extend Container. class 12kgBox extends Box implements $4.

Almost got it boys

A perfect task to flex dat Prolog knowledge. Too bad I forgot Prolog.

>Napsack problem
>Napsack
Do you go to kindergarden user

Attached: kirinolaugh.gif (500x275, 1015K)

Sorry, I pronounce it "nap-sack", not "kuh-nap-sack" so I instinctively forget the K. Also I almost never use the word.

this is in every algorithms 101 class
what's your point

> A perfect task to flex dat Prolog knowledge
Usually Prolog is terrible with NP-complete problems.

Attached: np_complete.png (640x414, 108K)

>People using OOP in algortihms problems
ibm.com/developerworks/library/j-seqalign/

When in doubt, use brute force.
>Ken Thompson

try to put them for every possible combination recursively,
backtrack when next item exceeds maximum weight of a backpack,
keep track of the "combination that yields best result",
return it at the end of a function,
pray that the quantity of items and number of function calls won't burst the stack.

please no bully if it's stupid, I'm not a "professional programmer"

#include
#include

#define ARRAYSIZE(a) (sizeof(a) / sizeof(a[0]))

#define BIT(bit) (1 weight_max ? -1 : value;
}

static void solve_knapsack(struct container* sack, size_t size, unsigned weight_max) {
uint64_t map = 0;
int hightest = 0;

for (uint64_t i = 0; i < (1 hightest) {
hightest = value;
map = i;
}
}

for (int i = 0; i < size; ++i)
if (BIT_CHK(map, i))
printf("[$%d, %dkg] ", sack[i].value, sack[i].weight);
printf("\nTotal: $%d\n", hightest);
}

int main(void) {
struct container knapsack[] = {
{ 4, 12},
{ 2, 2},
{ 1, 1},
{ 2, 1},
{10, 4}
};

solve_knapsack(knapsack, ARRAYSIZE(knapsack), 15);

return 0;
}

gives

cc -Wall -Wpedantic knapsack.c -o knapsack
./knapsack
[$12, 4kg] [$1, 1kg] [$4, 10kg]
Total: $17

Attached: LETS-C.jpg (280x397, 13K)

Wait you can have an item multiple times?

>mixed fruit 7 times
hope those smartass fuckers like fruit

Green blue and orange

OK, I'm officially a brainlet. I have tried, but there are several previous steps I don't yet have. This is one hell of a motivation for me though.
Thanks OP.

and when I put weight and value in the right order, it even prints the correct solution!

./knapsack
[$2, 2kg] [$1, 1kg] [$2, 1kg] [$10, 4kg]
Total: $15

please explain this code to me

What part do you not understand?

Heh, just had the same problem. Praised be vim-swap.
-- Adapted from rosettacode.org/wiki/Knapsack_problem/0-1#Haskell

inv = [("green box",12,4),("blue box",2,2),("grey box",1,2),("orange box",1,1),("yellow box",4,10)]

knapsack = foldr addItem (repeat (0,[])) where
addItem (name,w,v) list = left ++ zipWith max right newlist where
newlist = map (\(val, names)->(val + v, name:names)) list
(left,right) = splitAt w list

main = print $ (knapsack inv) !! 15

./knapsack
(15,["blue box","grey box","orange box","yellow box"])

I added some comments
#include
#include

#define ARRAYSIZE(a) (sizeof(a) / sizeof(a[0]))
#define BIT_CHK(val, bit) ((val) & (1