Knapsack Problems?

general
,
1

What are your favourite knapsack problems? Please link them in the answer. I just learnt the algo and would like to get proficient in it. Thanks :smiley:

1 Like
2
1 Like
3

this qn itself says it is knapsack problem, u can get ac in first attempt in this qn… easy one

5 Likes
4


nice problem of knapsack…:slight_smile:

3 Likes
5

it really helped

6

Some of them below are good :slight_smile:

https://codeforces.com/contest/364/problem/B

http://codeforces.com/problemset/problem/95/E

http://www.codeforces.com/problemset/problem/190/A

http://codeforces.com/problemset/problem/19/B

http://www.spoj.pl/problems/KNAPSACK/

http://code.google.com/codejam/contest/dashboard?c=90101#s=p2

http://community.topcoder.com/stat?c=problem_statement&pm=11511&rd=14545

http://pclub.in/index.php/wpc-archives/16-kodefest-solutions/86-problem-d

http://www.spoj.pl/problems/PIGBANK/

http://www.spoj.pl/problems/GNYR09F/

http://www.spoj.pl/problems/THREECOL/

http://www.spoj.pl/problems/SCUBADIV/

http://code.google.com/codejam/contest/dashboard?c=1128486

http://www.spoj.pl/problems/AE1B/

http://www.spoj.pl/problems/ARRANGE/

Will Add more to the List :slight_smile: if come across some Knapsack problems

6 Likes
7

Nice Collection :slight_smile:

8

perfect problem to start with knapsack thanq :slight_smile:

9

nice one :slight_smile:

10

what Knapsack itself. i have been looking around on the net, but could not understand the theory yet. i am a nwebie.
thnx

11

i think i found a helpful info here: http://www.programminglogic.com/knapsack-problem-dynamic-programming-algorithm/

12

This is a pretty good simple knapsack problem: http://www.codechef.com/problems/PPTEST/

Another slightly tougher knapsack problem: www.spoj.com/problems/BACKPACK/

2 Likes
13

Solve this http://www.spoj.com/problems/PARTY/
Good way to start DP and knapsack type problem

2 Likes
14

Are you sure each of the above problems is an application of knapsack? I have solved some of them and i don’t think so. For example-

  1. MIXTURES - Matrix Chain Multiplication
  2. AGGRCOW - Binary search
  3. STAMPS, BAISED - Adhoc
1 Like
15

I don’t think MINUS on SPOJ is knapsack either.

1 Like
16

Wow!! Instead of replying to our queries, you just edited your answer and made aur questions look stupid. Now what will you do if i say that the problem AE1B is also adhoc ?

17

really nice one

18

pale_rider plz look problem carefully then surely u will understand that MINUS on spoj is knapsack :wink: :stuck_out_tongue: infinitum really nice collection :smiley: