задача про рюкзак

  • Автор темы biv171
  • Дата начала
Статус
Закрыто для дальнейших ответов.
B

biv171

#1
ребят если можете помогите плиз,я тока начал(пытаюсь) программировать на С и столкнулся вот с чем,задача у меня про рюкзак,решаю я эту задачу с помощью наивного алгоритма , т.е перебираю все возможные варианты так если вещей 3 ,то 001,010,011,100,101,110,111..вроде как все компилируется,а ответ неправильный(в коде я вроде как уверен все логично)т.е например:нам дан максимальный вес 6 кг вещей у нас три : 1кг ,2кг, 3кг т.е ответ д/б [1 1 1]..

подскажите пожайлуста где я еще накосячил???
Код:
#include <stdio.h>
#include <stdlib.h >

void prt(int n,int s);


int main()
{
int i,a[20],s,n;

printf("Vvedite kolichestvo elementov= ");
scanf("%d",&n);

printf ("vvedite elementi a[i]: ");
for(i=1;i<=n;++i)
scanf("%d",&a[i]);
//for (i=1;i<n;++i)
//	printf("%d",a[i]);

printf("vvedite symmy S= ");
scanf("%d",&s);

prt(n,s);


}

void prt(int n,int s)
{
int flag,sum,p,i,j;
int a[20];
int e[20];
int ans[20][20];

flag=0;
for(i=1;i<n;++i)
e[i]=0;
p=0;
while (flag==0) {
i=1;
if (e[i]==0) 
e[i]=1;
else {
while (e[i]==1)	{
e[i]=0;
++i;
}

e[i]=1;
}

flag=1;
for(j=1;j<n;++j) {
flag=e[j]*flag;
}

sum=0;
for(j=1;j<n;++j)
sum=a[j]*e[j] + sum;
if (s==sum) {
++p;
for(j=1;j<n;++j)
ans[p][j]=e[j];
}
} 

if (p>0){
for(j=1;j<p;++j)
{
printf("[");
for(i=1;i<n;++i)
printf( "%d",ans[j][i]);
printf("]\n");
}
}
else printf("net reshenia\n");

}
 
D

Dimmuborgir

#2
если чесно, я не понял что надо найти. но могу сказать точно что будет полная попа если ввести n=21 или больше).
 
B

biv171

#3
хорошо,задано:
1)s=6кг -максимальный вес который мы можем взять.
2)массив a -данный массив содержит количество вещей и их вес,так например n=3 -количество вещей ,а элементы массива a их вес например первая вещь 1кг,вторая вещь 2кг,третья 3 кг. Т.е мы имеем массив a который "условно"выглядит так: [1,2,3]
Найти:
используя наивный алгоритм(перебором всех решений) найти решение,т.е т.к. у нас 3 вещи =>мы можем иметь 7 предполагаемых "вариантов-решений" (массив e=(001,010,011,100,101,110,111) и дальше перебором всех вариантов мы и занимаемся ,т.е:
1ый вариант: e=[0,0,1] и a=[1,2,3] => e*a=0*1+0*2+0*3=0, пото сравниваем равно ли это нашему максимальному весу т.е 6 кг нет не ровно значит это не решение...
2ой вариант: e=[0,1,0] и a=[1,2,3]=.e*a=...=2 => 2 не равно 6 -это не решение
3ий вариант....[0,1,1]....будет равно 5 -это тоже не решение
.....
и так проходим каждый вектор (001,010,011,100,101,110,111) решением задачт будет как раз этот вектор
в данном случае решением является вектор

[1,1,1]-вот что должно появится в конце!
надеюсь обьяснил понятно?

естественно вещей может быть и двадцать ,3 вещи я взял для простоты!
 

Vadik(R)

Well-known member
12.12.2007
469
0
#4
Делай трассировку, больше ничего не могу сказать. Да, задачи на динамическое программирование тем и сложны, что поначалу надо придумать характеристику какого-то состояния, написать программу, а потом искать косяки :)
 
Статус
Закрыто для дальнейших ответов.