Добавьте ints, но выберите ближайший к числу, который я хочу

Я сижу здесь и пытаюсь выполнить эту задачу.
(https://open.kattis.com/problems/walrusweights)Добавьте ints, но выберите ближайший к числу, который я хочу

Первый вход содержит количество пластин следует использовать (INT).
РАСЧ после являются пластины (вес), и каждый из них должен быть < = 1000.
Добавить РАСЧ вместе и попытаться так близко к 1000, насколько это возможно, НО
в случае существует два таких числа, которые одинаково близко к 1000, (998 и 1002), затем выбирайте большую.

Говорят, что у меня есть 4 тарелки, то первый из них 4, 900, 500, 498.
Складывая их, так что вы пришли как можно ближе к 1000. 498 + 500 = 998.
500 + 498 + 4 = 1002.
В этом случае выбирают 1002.

int sum=0; 
Scanner scan = new Scanner(System.in); 
int count = scan.next(); 
for(int i = 0; i < count; i++) 
{ 
    sum = sum + scan.next(); 
}

или

Scanner scan = new Scanner(System.in); 
int count = scan.nextInt(); 

while(count > 0) { 
//your logic 
count--; 
}

Я попытался, но не понимаю логику/алгоритм сравнения добавленных чисел, и если они равны, выберите более высокий. Все, что я получаю, это то, что я могу положить счетчик и весы, и это добавит его, может кто-нибудь объяснить, как сделать алгоритм? Что я должен прочитать, чтобы понять это?

спасибо.

источник

2015-12-15 DMT82

Знаете ли вы, что-нибудь о динамическом программировании раньше? –

Я сижу здесь с тремя книгами Java и пытаюсь понять Алгоритмы и как это работает, прочитал 2 из них, но ничего о динамическом программировании. У вас есть хороший совет/книги, сайты? Буду признателен, благодарю вас. – DMT82

Вы можете взглянуть на [это] (https: //www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced /) или [this] (https://www.codechef.com/wiki/tutorial-dynamic-programming) –

Это проблема динамического программирования, и это первое, что нужно для Google, если вы не знакомы с этим подходом. Идея в этой задаче состоит в создании массива A размера 2001 (обратите внимание, что любой возможный ответ меньше или равен 2000). Первоначально, A[0] = true и для всех других индексов A[i] = false. Затем для каждой пластины вы повторяете от 1000 до 0 и, если A[i] == true, то A[i + currentWeight] = true. Таким образом вы вычисляете, какие общие веса можно получить с вашими тарелками. В конце вы найдете индекс x такой, что A[x] == true и (x - 1000) как можно меньше (в случае жеребьевки вы берете наибольший такой x).

источник

2015-12-15 18:01:19 Ardavel

Большое вам спасибо. Думаю, вы имели в виду 1000, а не 2000, но еще раз спасибо, поймаем его и прочитаем о динамическом программировании и как использовать массивы таким образом. – DMT82

Спасибо, вы можете перебирать от 1000 до 0, но ваш массив должен иметь размер больше 1000, потому что возможное решение может превышать 1000, как в примере набора данных в задаче. – Ardavel

Поскольку массив, вероятно, будет разреженным, т. Е. Будет истинно только несколько значений, поиск истинных значений будет медленным. В более эффективном решении можно использовать «TreeMap» или отсортированный массив. – Andreas

Как Арманд предлагает, это называется динамическим программированием.
Одна из известных проблем - проблема Knapsack, другая - Dijkstra - алгоритм для кратчайшего пути.

Основная идея этого подхода состоит в том, чтобы разбить подзадачи и сохранить подвыборы. Вы решаете каждую подзадачу один раз и сохраняете свои решения в поиске.
В следующий раз, когда возникает одна и та же подзадача, вместо повторного вычисления ее решения вы используете поиск и экономя время и память.
В вашем случае вы суммируете подэлементы в аналогичном вопросе с проблемой Рюкпак.

источник

2015-12-15 19:12:09

Добавьте ints, но выберите ближайший к числу, который я хочу

ответ

Смежные вопросы