时间戳

首页 > 解决方案 > 无需递归即可找到总和等于或小于给定数字的最大子集

java - 无需递归即可找到总和等于或小于给定数字的最大子集

问题描述

有一个Product具有属性的对象price，也给出了一个budget。

从产品列表和给定预算中，如何获得价格总和等于或小于预算的最长产品子集。每个子集只允许 1 个产品。价格和预算总是积极的

例如

   [
      {id: 1, name: pr1, price: 1},
      {id: 2, name: pr2, price: 1},
      {id: 3, name: pr3, price: 1.5},
      {id: 4, name: pr4, price: 3},
      {id: 5, name: pr5, price: 2},
      {id: 6, name: pr6, price: 4},
   ]

预算 = 6

结果

  [
      {id: 1, name: pr1, price: 1},
      {id: 2, name: pr2, price: 1},
      {id: 3, name: pr3, price: 1.5},
      {id: 5, name: pr5, price: 2},
  ]

有没有可能在不递归的情况下解决这个问题

标签： javajava-8

解决方案

正如乔丹在评论中所说，贪婪的解决方案会奏效。假设一个排序列表products：

int sum = 0;
List<Product> subset = new ArrayList<>();
for (Product p : products) {
  if (sum + p.price <= budget) {
    subset.add(p);
    sum += p.price;
  } else return subset;  // or break
}

通过首先添加最便宜的产品，您可以保证在达到预算之前可以安装尽可能多的产品。

推荐阅读