X
Xyz1
Gast
Ich brauchte etwas bis ich das "nachstellen" konnte. Bitte nicht ärgern dass dort keine Getter/Setter sind.
Gesucht ist eine profitable Reise zwischen zwei Orten. Also, ich hätte gern gewusst wie sich die Schleife an der O(3) steht vereinfachen lässt bzw. ob es bessere Alternativen dazu gibt bzw. was der Suchbegriff dazu ist. Und auch ob das Problem np-schwer ist. Und auch wie eine Reise zwischen n Orten aussehen würd.
Gesucht ist eine profitable Reise zwischen zwei Orten. Also, ich hätte gern gewusst wie sich die Schleife an der O(3) steht vereinfachen lässt bzw. ob es bessere Alternativen dazu gibt bzw. was der Suchbegriff dazu ist. Und auch ob das Problem np-schwer ist. Und auch wie eine Reise zwischen n Orten aussehen würd.
Java:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
public class Trading {
static ArrayList<Place> places = new ArrayList<>();
public static void main(String[] args) {
Random r = new Random(0);
for (int i = 0; i < 100; i++) {
Place p = new Place();
p.x = r.nextInt(201) - 100;
p.y = r.nextInt(201) - 100;
p.z = r.nextInt(201) - 100;
int a = r.nextInt(10) + 3;
int b = r.nextInt(10) + 3;
int c = r.nextInt(10) + 3;
p.to_buy.add(new Product("a", a));
p.to_buy.add(new Product("b", b));
p.to_buy.add(new Product("c", c));
p.to_sell.add(new Product("a", a - 3));
p.to_sell.add(new Product("b", b - 3));
p.to_sell.add(new Product("c", c - 3));
places.add(p);
}
// O(3)
ArrayList<Object[]> re = new ArrayList<>();
for (int i = 0; i < places.size(); i++) {
Place a = places.get(i);
for (int j = i + 1; j < places.size(); j++) {
Place b = places.get(j);
if (a.dista(b) <= Place.max_dista) {
for (Product c : a.to_buy) {
if (c.price > 0) {
for (Product d : b.to_sell) {
if (c.name.equals(d.name) && d.price > c.price) {
for (Product e : b.to_buy) {
if (e.price > 0) {
for (Product f : a.to_sell) {
if (e.name.equals(f.name) && f.price > e.price) {
re.add(new Object[] { a, b, c, d, e, f });
}
}
}
}
}
}
}
}
}
}
}
Collections.sort(re, new Comparator<Object[]>() {
@Override
public int compare(Object[] o1, Object[] o2) {
return (((Product) o2[3]).price - ((Product) o2[2]).price + ((Product) o2[5]).price - ((Product) o2[4]).price)
- (((Product) o1[3]).price - ((Product) o1[2]).price + ((Product) o1[5]).price - ((Product) o1[4]).price);
}
});
for (Object[] o : re) {
System.out.println(Arrays.toString(o));
// System.out.println(((Place) o[0]).dista((Place) o[1]));
// System.out.println(((Product) o[3]).price - ((Product) o[2]).price + ((Product) o[5]).price - ((Product) o[4]).price);
}
}
}
class Place {
int x, y, z;
List<Product> to_buy = new ArrayList<>();
List<Product> to_sell = new ArrayList<>();
static final int max_dista = 7500;
int dista(Place o) {
return (x - o.x) * (x - o.x) + (y - o.y) * (y - o.y) + (z - o.z) * (z - o.z);
}
@Override
public String toString() {
return String.format("Place [x=%s, y=%s, z=%s]", x, y, z);
}
}
class Product {
String name;
int price;
Product(String n, int p) {
name = n;
price = p;
}
@Override
public String toString() {
return String.format("Product [name=%s, price=%s]", name, price);
}
}
