VPF::вопрос по видимости полей класса

Pawl

Дата 29.12.2011, 16:37 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 7
Всего: 28

господа,
недавно нашел код на 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 = current;

отработала некорректно. Если вместо нее написать

Код


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(), непосредственно перед выходом из него, они выводятся как надо!

--------------------

В действительности всё совсем не так, как на самом деле

jk1

Дата 29.12.2011, 16:49 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 1168
Регистрация: 17.10.2008
Где: Санкт-Петербург

Репутация: 40
Всего: 75

Вот этот код

Цитата

max = current;

приводит к тому, что теперь обе ссылки указывают на один и тот же объект в памяти.
После этого Вы затираете значения в current, соответственно и по ссылке max тоже будут нули.

Этот код

Код


max.mass = current.mass;
max.price = current.price;

не присваивает ссылок, а просто копирует поля, то есть две разные ссылки будут и дальше указывать на два конкретных объекта. И обнуление полей current никак не скажется на max.

Это сообщение отредактировал(а) jk1 - 29.12.2011, 16:50

--------------------

Opinions are like assholes — everybody has one

Pawl

Дата 29.12.2011, 18:06 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 7
Всего: 28

да, но почему тогда работает

Код


        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;
            }
        }

ведь тут тот же принцип?

--------------------

В действительности всё совсем не так, как на самом деле

jk1

Дата 29.12.2011, 18:20 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 1168
Регистрация: 17.10.2008
Где: Санкт-Петербург

Репутация: 40
Всего: 75

Цитата

ведь тут тот же принцип?

В этот раз Вы выводите значения из max до того, как обнулили current. Обнуление происходит вот тут:

Код


currentItems.pop();
current.mass -= items.get(i).mass;
current.price -= items.get(i).price;

Соответственно до этого момента в max можно найти корректный результат, а после уже нет.

--------------------

Opinions are like assholes — everybody has one

Pawl

Дата 29.12.2011, 18:34 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 7
Всего: 28

Код


            if (current.price > max.price) {   
                optItems = new Item[currentItems.size()];
                currentItems.toArray(optItems);
                max = current;
                if (current.mass == max.mass) {
                    ending = true;
                }
                    
                return;
            }

if (current.price > max.price) - условие выполнилось, max = current; и return; - max ссылается на current. - где тут обнуление current?

--------------------

В действительности всё совсем не так, как на самом деле

jk1

Дата 29.12.2011, 20:48 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 1168
Регистрация: 17.10.2008
Где: Санкт-Петербург

Репутация: 40
Всего: 75

Цитата

где тут обнуление current?

Обнуление происходит за счет последовательного вычитания при возврате рекурсии.
Да, там где нашли максимум был сделан return. Теперь смотрим внимательно откуда при этом вызывался метод next() - из строки 65 Вашего примера наверху. Вот он возвращает, а дальше

Код


currentItems.pop();
current.mass -= items.get(i).mass;
current.price -= items.get(i).price;

ну и так до тех пор, пока не развернется вся рекурсивная цепочка.

Не верите мне - запустите отладчик и убедитесь сами.

--------------------

Opinions are like assholes — everybody has one

Pawl

Дата 29.12.2011, 21:25 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 7
Всего: 28

Цитата(jk1 @ 29.12.2011, 20:48

)

запустите отладчик и убедитесь сами.

Ок, убедился, спасибо! smile

Можно тогда не по теме? Вот код на шарпе, который я переделывал:

Код


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1 {
    struct Item {
        public double mass;
        public double price;

        public override string ToString() {
            return String.Format("Цена {0}, Масса: {1}", price, mass);
        }
    }

    class Program {
        // Число предментов в рюкзаке
        const int n = 5;
        // Ограничение по массе
        const int maxMass = 10;
        static bool ending = false;
        static List<Item> items;
        static Stack<Item> currentItems = new Stack<Item>();
        static Item current = new Item();
        static Item[] optItems = null;
        static Item max = new Item();
        static Random rnd = new Random(1);

        static int ComparerItemMass(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;
        }

        static void next(int i) {
            i++;

            if ((i > items.Count - 1) || (current.mass + items[i].mass > maxMass)) {
                if (current.price > max.price) {
                    optItems = currentItems.ToArray();
                    max = current;
                    if (current.mass == max.mass)
                        ending = true;
                    return;
                }
            }

            currentItems.Push(items[i]);
            current.mass += items[i].mass;
            current.price += items[i].price;
            next(i);

            currentItems.Pop();
            current.mass -= items[i].mass;
            current.price -= items[i].price;
            if (ending != true)
                next(i);
        }

        static void Main(string[] args) {
            items = new List<Item>(n);
            for (int i = 0; i < n; i++) {
                Item item = new Item();
                item.mass = rnd.Next(1, 10);
                item.price = rnd.Next(1, 10);
                items.Add(item);
            }
            items.Sort(ComparerItemMass);

            Console.WriteLine("Исходные данные (отсортированы по удельной стоимости):");
            foreach (Item it in items)
                Console.WriteLine(it);

            Console.WriteLine("");
            Console.WriteLine("------------------");
            Console.WriteLine("");
            Console.WriteLine("Оптимальный набор туриста:");

            max.price = -1;
            next(-1);

            if (optItems != null) {
                foreach (Item it in optItems)
                    Console.WriteLine(it);
                Console.WriteLine("Итого:");
                Console.WriteLine(max);
            }
            else
                Console.WriteLine("Что-то не так...");

            Console.ReadKey();
        }
    }
}

как видно, здесь в методе next() так же есть строчка max = current; но тут-то это прокатывает! Может, потому, что Item не class а struct? В яве структур нету, поэтому я не совсем представляю разницу. В NETe я кое-что про это нарыл, но всё-равно толком не въехал! smile

--------------------

В действительности всё совсем не так, как на самом деле

jk1

Дата 29.12.2011, 22:05 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 1168
Регистрация: 17.10.2008
Где: Санкт-Петербург

Репутация: 40
Всего: 75

Структуры копируются при присваивании. При присваивании структуры к новой переменной выполняется копирование всех данных, а любое изменение новой копии не влияет на данные в исходной копии.
В Java структур нет, так что переносить алгоритм, заменяя структуры классами, не всегда безопасно.

--------------------

Opinions are like assholes — everybody has one

Pawl

Дата 29.12.2011, 23:58 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 7
Всего: 28

Спасибо!

--------------------

В действительности всё совсем не так, как на самом деле

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »