TopCoder problem solution: ChristmasBatteries

This post provides a solution to the TopCoder problem of ChristmasBatteries. 

This problem can be modeled as a 0-1 Knapsack problem. We can mode each toy as an item that can be put into the knapsack. The total weight allowed in the knapsack is the total number of available batteries. Each toy has two properties: fun and required batteries. The "fun" parameter is the value of the item. The required batteries is the weight of the item. The ChristmasBatteries problem can be solved by finding a subset of the toys that will maximize the fun while subjected to the constraint of the total number of available batteries.

Note that the number of batteries is an integer, this is crucial for the Dynamic Programming solution to work.

Implementation of the 0-1 Knapsack problem using Dynamic Programming 

First, we define an interface that represents a single abstract item that can be stored in a knapsack:

public interface KnapsackItem {
    double getValue();
    int getWeight();
}

Then we define a generic class for solving the 0-1 Knapsack problem:

/**
 * Solves the 0-1 knapsack problem using Dynamic Programming (DP).
 * <p>
 * Solution is derived from <a href="">Wikipedia entry of the Knapsack problem</a>.
 * <p>
 * Modified the algorithm for finding the chosen items from the original recursive method to an iterative method.
 */
@RequiredArgsConstructor
public class ZeroOneKnapsack {
    /**
     * The total capacity of the knapsack.
     */
    private final int capacity;

    public <T extends  KnapsackItem> List<T> selectItems(Collection<T> items) {
        // Discard all the items that are bigger than the capacity, there is no way that they can fit there.
        // Also discard items with non-positive values, there is no need to keep them there either.
        List<T> eligibleItems = items
            .stream().filter(item -> item.getWeight() <= capacity && item.getValue() > 0)
            .collect(Collectors.toList());

        double[][] values = new double[eligibleItems.size() + 1][capacity + 1];
        // Each column of the 2D array represents the fixed weight j (j's range is [0, capacity]).
        for (int i = 0; i <= capacity; i++) {
            values[0][i] = 0;
        }

        // Now calculate the total values for selecting each item.
        for (int i = 1; i <= eligibleItems.size(); i++) {
            double vi = eligibleItems.get(i - 1).getValue();
            int wi = eligibleItems.get(i - 1).getWeight();
            for (int j = 0; j <= capacity; j++) {
                if (wi > j) {
                    values[i][j] = values[i - 1][j];
                // If we choose this item, then the total value of the sack is the sum of the
                // value of this item and the sum of the values added before this item.
                } else {
                    values[i][j] = Math.max(values[i - 1][j], values[i - 1][j - wi] + vi);
                }
            }
        }

        // Now figure out the items that are chosen.
        List<T> chosenItems = Lists.newArrayList();
        int weightLeft = capacity;
        for (int i = eligibleItems.size() - 1; i >= 0; i--) {
            if (values[i + 1][weightLeft] > values[i][weightLeft]) {
                chosenItems.add(eligibleItems.get(i));
                weightLeft = weightLeft - eligibleItems.get(i).getWeight();
            }
        }

        return chosenItems;
    }
}

Solution to the ChristmasBatteries problem

/**
 * Solves the TopCoder problem of ChristmasBatteries.
 * @see <a href="https://community.topcoder.com/stat?c=problem_statement&pm=16717"/>
 */
public class ChristmasBatteries {
    public int mostFun(int totalBatteries, int totalToys, int x, int y, int z, int m) {
        List<Toy> toys = Lists.newArrayList();

        for (int i = 0; i < totalToys; i++) {
            toys.add(new Toy(i, x, y, z, m));
        }

        return (int) (new ZeroOneKnapsack(totalBatteries).selectItems(toys).stream().mapToLong(Toy::getFun).sum());
    }

    @Test
    public void test0() {
        Assert.assertEquals(1, mostFun(0, 5, 1, 1, 1, 1000));
    }

    @Test
    public void test1() {
        Assert.assertEquals(14, mostFun(3, 5, 1, 1, 1, 1000));
    }

    @Test
    public void test2() {
        Assert.assertEquals(11, mostFun(3, 5, 1, 1, 1, 13));
    }

    @Test
    public void test3() {
        Assert.assertEquals(0, mostFun(4, 10000, 123, 456, 789, 1));
    }

    @Test
    public void test4() {
        Assert.assertEquals(100, mostFun(7, 4, 3, 5, 7, 997));
    }

    @Test
    public void test5() {
        Assert.assertEquals(143371, mostFun(2, 12345, 234, 34, 5, 117));
    }

    @Value
    private static class Toy implements KnapsackItem {
        long serialNumber;
        long fun;
        int batteries;

        public Toy(long serialNumber, long x, long y, long z, long m) {
            this.serialNumber = serialNumber;
            batteries = (int)(serialNumber % 5);
            // (x + y) % m = ((x % m) + (y % m)) % m
            // See https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-addition-and-subtraction
            fun = (((((x * serialNumber) % m) * serialNumber) % m)
                + ((y * serialNumber) % m)
                + (z % m)) % m;
        }

        @Override
        public double getValue() {
            return fun;
        }

        @Override
        public int getWeight() {
            return batteries;
        }
    }
}

Java Imports

Lombok is used in this code example for generating constructors and getters. Google Guava is used in this code example for generating immutable lists. JUnit is used for running test cases.

import com.google.common.collect.Lists;

import lombok.RequiredArgsConstructor;
import lombok.Value;
import org.junit.Assert;
import org.junit.jupiter.api.Test;

import java.util.List;
import java.util.Collection;
import java.util.stream.Collectors;