господа,
недавно нашел код на C#, описывающий задачу о рюкзаке. К слову, алгоритм не идеальный, но речь о другом. В учебно-воспитательных целях переложил его на яву, и вот что у меня получилось:
| Код |
import java.util.*;
public class Zack {
// Число предментов в рюкзаке
private final int N = 5;
// Ограничение по массе
private final int MAX_MASS = 10;
private boolean ending = false;
private ArrayList<Item> items = new ArrayList<Item>(N);
private Stack<Item> currentItems = new Stack<Item>();
private Item current = new Item(), max = new Item();
private Item [] optItems;
private Random rnd = new Random(1);
public Zack() {
for (int i = 0; i < N; i++) {
Item item = new Item();
item.mass = rnd.nextInt(10);
item.price = rnd.nextInt(10);
items.add(item);
}
Collections.sort(items, comparerItemMass);
}
class Item {
public float mass;
public float price;
public String toString() {
return String.format("%s %.1f %8s %.1f", "Цена:", price, "Macca:", mass);
}
}
// сортировка по удельной стоимости предметов
private Comparator<Item> comparerItemMass = new Comparator<Item>() {
public int compare (Item a, Item b) {
if (a.price / a.mass > b.price / b.mass) {
return -1;
}
if (a.price / a.mass < b.price / b.mass) {
return 1;
}
return 0;
}};
public void next(int i) {
i++;
if ((i > items.size() - 1) || (current.mass + items.get(i).mass > MAX_MASS)) {
if (current.price > max.price) {
optItems = new Item[currentItems.size()];
currentItems.toArray(optItems);
max = current;
if (current.mass == max.mass) {
ending = true;
}
return;
}
}
currentItems.push(items.get(i));
current.mass += items.get(i).mass;
current.price += items.get(i).price;
next(i);
currentItems.pop();
current.mass -= items.get(i).mass;
current.price -= items.get(i).price;
if (ending != true) {
next(i);
}
}
public static void main(String[] args) {
Zack z = new Zack();
System.out.println("Исходные данные (отсортированы по удельной стоимости):");
for (Item item : z.items) {
System.out.println(item);
}
System.out.println("");
System.out.println("------------------");
System.out.println("");
System.out.println("Оптимальный набор туриста:");
z.next(-1);
if (z.optItems != null) {
for (Item item : z.optItems) {
System.out.println(item);
}
System.out.println("Итого:");
System.out.println(z.max);
} else {
System.out.println("Что-то не так...");
}
}
}
|
а вот вывод этой программы:| Цитата |
Исходные данные (отсортированы по удельной стоимости):
Цена: 8,0 Macca: 5,0
Цена: 6,0 Macca: 4,0
Цена: 4,0 Macca: 4,0
Цена: 8,0 Macca: 8,0
Цена: 3,0 Macca: 7,0
------------------
Оптимальный набор туриста:
Цена: 8,0 Macca: 5,0
Цена: 6,0 Macca: 4,0
Итого:
Цена: 0,0 Macca: 0,0
|
как видно строчка
отработала некорректно. Если вместо нее написать| Код |
max.mass = current.mass;
max.price = current.price;
|
то вывод итогов будет правильным:| Цитата |
Итого:
Цена: 14,0 Macca: 9,0
|
также корректно напечатается итог, если его вывод делать непосредственно в методе next(), т. е.| Код |
if ((i > items.size() - 1) || (current.mass + items.get(i).mass > MAX_MASS)) {
if (current.price > max.price) {
optItems = new Item[currentItems.size()];
currentItems.toArray(optItems);
max = current;
if (current.mass == max.mass) {
ending = true;
}
System.out.println("Итого:");
System.out.println(max);
return;
}
}
|
вот мне и непонятно, что же мешает после операции max = current; вывести значения полей mass и price объекта max в методе main? Ведь в методе next(), непосредственно перед выходом из него, они выводятся как надо! |
Можно тогда не по теме? Вот код на шарпе, который я переделывал:
