有一個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}, ]是否可以不用遞歸解決這個問題
3 回答
DIEA
TA貢獻1820條經驗 獲得超2個贊
聽起來像面試題。示例是對價格進行排序，因此您將有 {1,1,1.5,2,3,4} 然后您只需繼續將項目添加到列表中，而總和小于預算。爪哇：
public static void main(String[] args) {
ArrayList<Product> product = new ArrayList<>();
product.add(new Product(1, "pr1", 1));
product.add(new Product(2, "pr2", 1));
product.add(new Product(3, "pr3", 1.5));
product.add(new Product(4, "pr4", 3));
product.add(new Product(5, "pr5", 2));
product.add(new Product(6, "pr6", 4));
Price price = new Price(); // Custom comparator that compares two Products' price, must be defined elsewhere
Collections.sort(product, price);
ArrayList<Product> longest = new ArrayList<>();
for(int i=0; i < product.size(); i++) {
if(budget - product.get(i).price > 0) {
budget = budget - product.get(i).price;
longest.add(product.get(i));
}
}
}
紅顏莎娜
TA貢獻1842條經驗 獲得超13個贊
正如喬丹在評論中所說，貪婪的解決方案會奏效。假設一個排序列表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
}
通過首先添加最便宜的產品，您可以保證在達到預算之前可以容納盡可能多的產品。
哈士奇WWW
TA貢獻1799條經驗 獲得超6個贊
所以情況是這樣的：我寫了一個程序，它確實使用遞歸并且有點完成你正在尋找的東西。唯一的問題是它捕獲了最長的數字組合/子集，這些組合僅恰好等于目標總和（在您的示例中為 6）；我似乎無法弄清楚如何找到小于或等于目標總和的最長子集。此外，在您的示例中，價格有兩個 1。如果您運行我的程序實例，您會注意到它會將兩個子集（多于一個子集等于 6）視為具有相同的 id 1，因此它們是重復的子集。那是您可以解決的另一個問題。這個程序花了我一天多的時間才想出，所以即使它有問題并且使用遞歸，我還是想發布它。
import java.util.*;
public class SubSet_sum_problem
{
private static ArrayList<int[]> listOfArrays = new ArrayList<int[]>();
public static void getSubsets(double[] elements, double sum) {
getAllSubsets(elements, 0, sum, new Stack<Double>());
}
private static void getAllSubsets(double[] elements, int i, double sum, Stack<Double> currentSol) {
//stop clauses:
if (sum == 0 && i == elements.length)
{
Object[] prices = currentSol.toArray();
double[] prices2 = new double[currentSol.size()];
for (int index = 0; index < prices.length; index++)
prices2[index] = (Double)prices[index];
int[] indexes = new int[currentSol.size()];
for(int index2 = 0; index2 < prices2.length; index2++) { // Find common/duplicate elements in both arrays
for(int count = 0; count < elements.length; count++) {
if(prices2[index2] == elements[count])
indexes[index2] = count;
}
}
for (int a = 0; a < indexes.length; a++) // Scanning for duplicates again, this time for common indexes
{
for (int b = a + 1; b < indexes.length; b++)
{
if (indexes[a] == indexes[b]) // Now we know we have duplicate indexes for the elements[] array, which isn't possible
{
indexes[a] = a;
indexes[b] = b;
}
}
}
listOfArrays.add(indexes);
}
//if elements must be positive, you can trim search here if sum became negative
if (i == elements.length)
return;
//"guess" the current element in the list:
currentSol.add(elements[i]);
getAllSubsets(elements, i+1, sum-elements[i], currentSol);
//"guess" the current element is not in the list:
currentSol.pop();
getAllSubsets(elements, i+1, sum, currentSol);
}
public static void main(String args[])
{
String name[] = {"pr1", "pr2", "pr3", "pr4", "pr5", "pr6"};
double price[] = {1, 1, 1.5, 3, 2, 4};
double sum = 6.0;
getSubsets(price, sum);
int size = listOfArrays.size();
int max = listOfArrays.get(0).length;
for(int str[] : listOfArrays)
{
int theSize = str.length;
if(max < theSize)
max = theSize;
}
for(int arr[] : listOfArrays)
{
if (arr.length == max)
{
for (int index = 0; index < arr.length; index++)
{
int index2 = arr[index] + 1;
System.out.print("{id: " + index2 + ", name: " + name[arr[index]] + ", price: " + price[arr[index]] + "}\n");
if (index == arr.length - 1)
System.out.print("\n");
}
}
}
}
}
添加回答
舉報
0/150
提交
取消