All Questions
19
questions
1
vote
0
answers
27
views
Knapsack with fixed number of bins?
Constant: d, a fixed number of bins/sacks
Input:
$v_1,v_2,...,v_n$ item profits,
$0<w_1,w_2,...,w_n\leq1$ item weights.
Output: $B_1,B_2,...,B_d$ which are d subsets of $\{1,2,...,n\}$ s.t. they ...
- 11
3
votes
1
answer
161
views
How to solve a given combinatorial problem?
Given $n$ balls, which are numbered from $1$ to $n$, and also $n$ boxes, which are also numbered from $1$ to $n$. Initially, $i$-th ball is placed at $i$-th box. Then we are doing the following ...
- 33
0
votes
0
answers
139
views
Arranging 3 types of balls with given conditions.
There are 3 types of balls black, white and green. Find the number of ways of arranging $n$ such balls such that
black, white adjacent pairs occur $a$ times,
black, green adjacent pairs occur $b$ ...
- 17
1
vote
2
answers
195
views
Finding the maximum value of elements to be selected in a grid - ZIO $2009$, P$1$
Hello Community! The above problem you see is a problem I got wrong. :( This is ZIO $2009$, P$1$.
I tried the problem and miserably found the wrong answer as $20$. Here is how my approach goes - part ...
- 779
3
votes
0
answers
332
views
Pseudo-polynomial algorithm for Bin-Packing with fixed number of bins
I'm looking for a pseudo-polynomial algorithm for the Bin-Packing Problem for a fixed number of bins $k$. I know we can use dynamic programming when the number of different sizes is fixed size since ...
- 297
5
votes
0
answers
121
views
Partition problem where partition are in increasing order.
For given $n$ and $S$, how many possible combinations are there such that:
$x_1 + x_2 + .. + x_n = S $ $\forall i, x_i \leq x_{i+1}$ $\&$ $x_i \geq 1$
For example, if $n$ = 3 and $S$ = 5, there ...
- 51
4
votes
1
answer
177
views
Combinations of red and black balls
Given $N$ Identical Red balls and $M$ Identical Black balls, in how many ways we can arrange them such that not more than $K$ adjacent balls are of same color.
Example : For $1$ Red ball and $1$ ...
- 41
1
vote
0
answers
587
views
Number of ways to partition an array of numbers so that the partition sums are equal and first part numbers are lesser than second part
This question is related to the famous combinatorics question on TopCoder called Jewelry
You are given an array of numbers :
$\{1,2,3,4,5,5\}$
The task is to count the number of ways that the array ...
- 1,025
1
vote
1
answer
482
views
Please explain how in the TSP, "every subpath of a path of minimum distance is itself a minimum distance"?
According to wikipedia, and many other sources I have read through, the Held-Karp algorithm is based on the idea that "every subpath of a path of minimum distance is itself a minimum distance."
I was ...
- 235
1
vote
0
answers
160
views
How would you prove that a dynamic programming problem is solvable by a greedy algorithm?
I have solved a few optimizations problems using dynamic programming, but some of those problems are also solvable by Greedy algorithms which are computationally more efficient to calculate.
For ...
- 1,025
1
vote
2
answers
216
views
Given an integer, how many ways can you divide into unequal portions
I have been thinking about this problem for a while but have been unable to formalize a complete answer.
Given an integer $n \geq 3$, how many different sets can you sum the integer elements in the ...
- 111
0
votes
0
answers
247
views
What is total possible no of subsets of a set with given n elements and max subset length possible is k
For Example let's say the given set is $\{1, 2, 3, 4\}$ i.e $n=4$ elements
and I have to find the subsets possible till the maximum length of $k=2$.
To do this i've to do All possible combinations ...
3
votes
3
answers
1k
views
Rod cutting: requesting a proof for $2^{n-1}$ possible ways
The rod cutting problem states that: Given a rod of length $n$ inches and a table of prices $P_i$ for $i=1,\dots,n$, determine the maximum revenue $R_n$.
In CLRS chapter 15 Rod cutting page 360:
...
- 33
1
vote
0
answers
79
views
number of strings which differ at atmost n positions?
I have been given a string T comprised of only 's','t','u','v' as characters .
I want to find numbers of strings with length |T| which differs at atmost n position from T. Also each such string must ...
- 11
0
votes
1
answer
406
views
Minimal sum of non-consecutive elements
I have $N$ numbers $a_i$. I want to find the smallest sum of EXACTLY $K$ non-consecutive elements. I know how to solve this in $O(N*K)$ (straightforward dynamic programing) but it is too slow. Anyone ...
- 1,591