Писал я что-то подобное, только там было немного сложнее, там были даны n1 чисел a, n2 чисел b и т. д. Решение искал перебором. Вот исходники, рабочие, если только это последние версии. Только как она работает не помню.
main.c
//если переполнение стека, то файл вывода пустой
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
//i-index s-size n-number
#define SARESULT 10
extern int timeout;
void inittimer(int ilimtime);
void destroytimer(void);
int t;
long lim;//максимальная сумма aresult[j] по j
long sum;//подбираемая сумма
long *acost;
long sacost;//размер массива цен, будет вводиться; не выходит за size_t
long *anumber;
long **aaresult;//массив вариантов подбора
long saresult = SARESULT;
long *aresult;//вариант подбора
long nresult = 0;//количество вариантов подбора, 0 < nresult <= SARESULT
long gdif = 4335;//текущая разность между sum и подобранной суммой
void perebor(long iacost, long ngood, long dif);
void saveresult(long dif);
void addresult(void);
void erase(void);
void outaaresult(void);
int inputdata(void);
main()
{
if(!inputdata()){
printf("error input");
return 1;
}
inittimer(t);
perebor(0, 0, sum);
destroytimer();
outaaresult();
return 0;
}
//iacost - индекс подбираемой цены
//ngood - уже подобранное количество товара
//dif - оставшаяся к подбору сумма
void perebor(long iacost, long ngood, long dif)
{
if(timeout)
return;
if(iacost == sacost){
//подбор закончен
saveresult(dif);
return;
}
aresult[iacost] = __min(dif / acost[iacost], __min(lim - ngood, anumber[iacost]));
for(;aresult[iacost] >= 0; aresult[iacost]--)
perebor(iacost + 1, ngood + aresult[iacost], dif - aresult[iacost] * acost[iacost]);
}
void saveresult(long dif)
{
if(gdif < dif)
return;
if(gdif == dif){
addresult();
return;
}
erase();
addresult();
gdif = dif;
}
void erase(void)
{
nresult = 0;
}
void addresult(void)
{
if(nresult < saresult){
memcpy(aaresult[nresult], aresult, sizeof(long) * (size_t)sacost);
nresult++;
}
}
void outaaresult(void)
{
long iaaresult1, iaaresult2;
#ifdef _DEBUG
printf("dif=%li\n", gdif);
printf("nresult=%li\n", nresult);
#endif
for(iaaresult1 = 0; iaaresult1 < nresult; iaaresult1++){
for(iaaresult2 = 0; iaaresult2 < sacost; iaaresult2++)
printf("%li ", aaresult[iaaresult1][iaaresult2]);
printf("\n");
}
#ifdef _DEBUG
{
long iacost;
for(iacost = 0; iacost < sacost; iacost++)
printf("%li\n", acost[iacost]);
for(iacost = 0; iacost < sacost; iacost++)
printf("%li\n", anumber[iacost]);
}
#endif
}
int inputdata(void)
{
//для распределения памяти
//sizeof(long) * (size_t)sacost и
//sizeof(long*) * (size_t)SARESULT
//должно вмещаться в тип size_t
long iacost, ianumber;
long iaaresult1;
scanf("t=%i", &t);
getchar();
scanf("lim=%li", &lim);
getchar();
scanf("sum=%li", &sum);
getchar();
scanf("sacost=%li", &sacost);
getchar();
if(sacost > 60000)
return 0;
acost = malloc(sizeof(long) * (size_t)sacost);
if(acost == NULL)
return 0;
scanf("acost=");
getchar();
for(iacost = 0; iacost < sacost; iacost++)
scanf("%li", acost + iacost);
getchar();
anumber = malloc(sizeof(long) * (size_t)sacost);
if(anumber == NULL)
return 0;
scanf("anumber=");
getchar();
for(ianumber = 0; ianumber < sacost; ianumber++)
scanf("%li", anumber + ianumber);
getchar();
aaresult = malloc(sizeof(long*) * (size_t)SARESULT);
if(aaresult == NULL)
return 0;
for(iaaresult1 = 0; iaaresult1 < SARESULT; iaaresult1++){
aaresult[iaaresult1] = malloc(sizeof(long) * (size_t)sacost);
if(aaresult[iaaresult1] == NULL)
return 0;
}
aresult = malloc(sizeof(long) * (size_t)sacost);
if(aresult == NULL)
return 0;
return 1;
}
time.c
#include <dos.h>
#include <stdio.h>
int timeout;
int timeis;//17 times per second
int limtime;
//ih-interrupt handler
//p-pointer
void (__interrupt __far *pihold)();
void __interrupt __far ihnew();
void inittimer(int ilimtime)
{
timeout = 0;
timeis = 0;
limtime = ilimtime * 17;
pihold = _dos_getvect(8);
_dos_setvect(8, ihnew);
}
void destroytimer(void)
{
_dos_setvect(8, pihold);
#ifdef _DEBUG
printf("t=%i\n", timeis);
#endif
}
void __interrupt __far ihnew()
{
timeis++;
if(timeis == limtime)
timeout = 1;
}
