be/src/kudu/util/knapsack_solver-test.cc

// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License.  You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing,
// software distributed under the License is distributed on an
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied.  See the License for the
// specific language governing permissions and limitations
// under the License.

#include <cstdlib>
#include <memory>
#include <string>
#include <vector>

#include <gtest/gtest.h>

#include "kudu/util/knapsack_solver.h"
#include "kudu/util/stopwatch.h"  // IWYU pragma: keep
#include "kudu/util/test_util.h"

using std::string;
using std::vector;

namespace kudu {

class TestKnapsack : public KuduTest {
};

// A simple test item for use with the knapsack solver.
// The real code will be solving knapsack over RowSet objects --
// using simple value/weight pairs in the tests makes it standalone.
struct TestItem {
  TestItem(double v, int w)
    : value(v), weight(w) {
  }

  double value;
  int weight;
};

// A traits class to adapt the knapsack solver to TestItem.
struct TestItemTraits {
  typedef TestItem item_type;
  typedef double value_type;
  static int get_weight(const TestItem &item) {
    return item.weight;
  }
  static value_type get_value(const TestItem &item) {
    return item.value;
  }
};

// Generate random items into the provided vector.
static void GenerateRandomItems(int n_items, int max_weight,
                                vector<TestItem> *out) {
  for (int i = 0; i < n_items; i++) {
    double value = 10000.0 / (random() % 10000 + 1);
    int weight = random() % max_weight;
    out->push_back(TestItem(value, weight));
  }
}

// Join and stringify the given list of ints.
static string JoinInts(const vector<int> &ints) {
  string ret;
  for (int i = 0; i < ints.size(); i++) {
    if (i > 0) {
      ret.push_back(',');
    }
    ret.append(std::to_string(ints[i]));
  }
  return ret;
}

TEST_F(TestKnapsack, Basics) {
  KnapsackSolver<TestItemTraits> solver;

  vector<TestItem> in;
  in.emplace_back(500, 3);
  in.emplace_back(110, 1);
  in.emplace_back(125, 1);
  in.emplace_back(100, 1);

  vector<int> out;
  double max_val;

  // For 1 weight, pick item 2
  solver.Solve(in, 1, &out, &max_val);
  ASSERT_DOUBLE_EQ(125, max_val);
  ASSERT_EQ("2", JoinInts(out));
  out.clear();

  // For 2 weight, pick item 1, 2
  solver.Solve(in, 2, &out, &max_val);
  ASSERT_DOUBLE_EQ(110 + 125, max_val);
  ASSERT_EQ("2,1", JoinInts(out));
  out.clear();

  // For 3 weight, pick item 0
  solver.Solve(in, 3, &out, &max_val);
  ASSERT_DOUBLE_EQ(500, max_val);
  ASSERT_EQ("0", JoinInts(out));
  out.clear();

  // For 10 weight, pick all.
  solver.Solve(in, 10, &out, &max_val);
  ASSERT_DOUBLE_EQ(500 + 110 + 125 + 100, max_val);
  ASSERT_EQ("3,2,1,0", JoinInts(out));
  out.clear();
}

// Test which generates random knapsack instances and verifies
// that the result satisfies the constraints.
TEST_F(TestKnapsack, Randomized) {
  SeedRandom();
  KnapsackSolver<TestItemTraits> solver;

  const int kNumTrials = AllowSlowTests() ? 200 : 1;
  const int kMaxWeight = 1000;
  const int kNumItems = 1000;

  for (int i = 0; i < kNumTrials; i++) {
    vector<TestItem> in;
    vector<int> out;
    GenerateRandomItems(kNumItems, kMaxWeight, &in);
    double max_val;
    int max_weight = random() % kMaxWeight;
    solver.Solve(in, max_weight, &out, &max_val);

    // Verify that the max_val is equal to the sum of the chosen items' values.
    double sum_val = 0;
    int sum_weight = 0;
    for (int i : out) {
      sum_val += in[i].value;
      sum_weight += in[i].weight;
    }
    ASSERT_NEAR(max_val, sum_val, 0.000001);
    ASSERT_LE(sum_weight, max_weight);
  }
}

#ifdef NDEBUG
TEST_F(TestKnapsack, Benchmark) {
  KnapsackSolver<TestItemTraits> solver;

  const int kNumTrials = 1000;
  const int kMaxWeight = 1000;
  const int kNumItems = 1000;

  vector<TestItem> in;
  GenerateRandomItems(kNumItems, kMaxWeight, &in);

  LOG_TIMING(INFO, "benchmark") {
    vector<int> out;
    for (int i = 0; i < kNumTrials; i++) {
      out.clear();
      double max_val;
      solver.Solve(in, random() % kMaxWeight, &out, &max_val);
    }
  }
}
#endif

} // namespace kudu