Проблема с лабораторной

[Двоешник]

Здравствуйте! Помогите мне пожалуйста с лабораторной работой за тот семестр=) По теории принятия решений=) Вообщем суть лабораторной - написать программу, можно на С, можно на С++, вообщем лишь бы она работала, даже на паскале можно=) Так вот задание следующее, Динамическое программирование, Покупатель имеет купюры достоинством A(1), ...,A(n), а продавец - B(1), .. ,B(m). Необходимо найти максимальную стоимость товара Р, которую покупатель не может купить, потому что нет возможности точно рассчитаться за этот товар с продавцом, хотя денег на покупку этого товара достаточно. Помогите пожалуйста=) Напишите желательно на Паскале, так проще=)

[dial595]

471-391-856
Пиши обсудим)) Буду рад помочь, тока я на C пишу))

[Анастасия18]

Если покупатель отдаст все свои купюры продавцу, то понятно, что для решения исходной задачи размер минимальной сдачи, которую продавец не может вернуть, используя любые имеющиеся теперь у него купюры C[i] (его и покупателя). Для этого удобно отсортировать купюры согласно их достоинства в порядке неубывания. Предположим, что продавец может вернуть любую сдачу от 1 до S, используя только меньшие i купюр. Для следующей (i+1)-ой купюры достоинства C[i+1] возможны 2 ситуации. 1. C[i+1]<S+2. Тогда понятно, что продавец может вернуть любую сдачу от 1 до C[i+1]+S, т.к. любая из этих сумм представима либо первыми i купюрами, либо (i+1)-ой купюрой вместе с некоторыми из первых i купюр. 2. C[i+1]>S+1. Тогда понятно, что продавец не может вернуть сдачу S+1. Опишем процедуру вычисления S. S:=0; i:=1; пока (i<=N) и (C[i]<=S+1) нц S:=S+C[i]; i:=i+1 кц Если значение S не меньше суммарного количества денег покупателя, то покупатель может купить товар любой доступной ему стоимости, точно рассчитавшись за покупку. Иначе P=A[1]+...+A[N]-S.
Почитай, может поможет!