Форум программистов, компьютерный форум CyberForum.ru

Задача о ранце - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
Нюша123
1 / 1 / 0
Регистрация: 11.10.2013
Сообщений: 63
19.02.2014, 10:01     Задача о ранце #1
Всем доброго времени суток!))Очень нужна помощь...решаю задачу о ранце,метод-динамическое программирование.Нужен код-решение на С++..может кто помочь чем-нибудь,буду очень благодарна!!!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.02.2014, 10:01     Задача о ранце
Посмотрите здесь:

о ранце C++
Задача о ранце. Исправить ошибки в приведенном коде C++
C++ Обратная задача о ранце (ДП)
C++ Задача о ранце
задача о ранце C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
19.02.2014, 12:47     Задача о ранце #2
например, эту задачу http://informatics.mccme.ru/mod/stat...apterid=3089#1
можно решать так

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct thing {
    int wght, cost;
};
 
int main()
{
    int n, W;
    cin >> n >> W;
    vector<thing> t(n);
    vector<int> weight(W+1, -1);
    for(int i=0; i < n; ++i)
        cin >> t[i].wght;
    for(int i=0; i < n; ++i)
        cin >> t[i].cost;
    weight[0] = 0;
    for(int i=0; i < n; ++i)
        for(int j=W - t[i].wght; j >= 0; --j)
            if(weight[j] != -1)
                weight[j + t[i].wght] = max(weight[j + t[i].wght], weight[j] + t[i].cost);
    cout << *max_element(weight.begin(), weight.end()) << endl;
    return exit_scs;
}
Нюша123
1 / 1 / 0
Регистрация: 11.10.2013
Сообщений: 63
19.02.2014, 15:15  [ТС]     Задача о ранце #3
А методом динамического программирования как это сделать?

Добавлено через 2 часа 20 минут
Либо генетический
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
19.02.2014, 15:20     Задача о ранце #4
мой код, конечно, не эталон, но тем не менее это динамика была)
Нюша123
1 / 1 / 0
Регистрация: 11.10.2013
Сообщений: 63
19.02.2014, 15:22  [ТС]     Задача о ранце #5
А,Спасибо А с генетическими когда-нибудь сталкивались?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
19.02.2014, 15:26     Задача о ранце #6
можно сказать, что нет. я почти на 100% уверен, что задача по ссылке грамотно написанным перебором будет решаться быстрее, чем какими-то модными методами.
Нюша123
1 / 1 / 0
Регистрация: 11.10.2013
Сообщений: 63
19.02.2014, 15:39  [ТС]     Задача о ранце #7
Есть вот такой код на Си генетический алгоритм решения задачи...Его нужно переделать на С++ и подправить немного...кто-нибудь сможет помочь?
Код
//Сам класс CDiophantine:
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <fstream>
#include <string>

#define MAXPOP	25
using namespace std;
class predmet
{
private:
	int w, p;
	string name;
public:
	predmet(){}
	void In(ifstream &ifst) 
	{
		ifst>>name;
		ifst>>w;
		ifst>>p;
	}
	void prin()
	{
		cout<<name<<" (Объем:"<<w<<" , Цена: "<<p<<" )\n";
	}
	int get_w(){return w;}
	int get_p(){return p;}
};

struct gene 
{
	int alleles[5];
	int fitness;
	float likelihood;

	// Проверка на равенство.
	int operator==(gene gn) 
	{
		for (int i=0;i<5;i++) 
		{
			if (gn.alleles[i] != alleles[i]) return false;
		}

		return true;
	}
};

class CDiophantine {
	public:
		CDiophantine(int, int, int, int, int, int);// Конструктор с коэффициентами A, B, C, D.
		int Solve();// Решить уравнение.
		
		//Возвращает данного гена.
		gene GetGene(int i) { return population[i];}

	protected:
		int ca,cb,cc,cd,ce;// The coefficients.
		int result;
		gene population[MAXPOP];// Population.

		int Fitness(gene &);// Fitness function.
		void GenerateLikelihoods();	// Generate likelihoods.
		float MultInv();// Creates the multiplicative inverse.
		int CreateFitnesses();
		void CreateNewPopulation();
		int GetIndex(float val);

		gene Breed(int p1, int p2);

};
void print(int* b)
{
	predmet A[100];
	ifstream ifst("input.txt");
	int n=0;
	for(;!ifst.eof();)
	{
		A[n].In(ifst);
		n++;
	}
	for(int i=0; i<n; i++) if(b[i]==1)
	A[i].prin();
}
CDiophantine::CDiophantine(int a, int b, int c, int d, int e, int res) : ca(a), cb(b), cc(c), cd(d), ce(e), result(res) {}

int CDiophantine::Solve() 
{
	int fitness = -1;
	// Генерация начальной популяции.
	srand((unsigned)time(NULL));
	for(int i=0;i<MAXPOP;i++)// Заполните населения с номерами между
	{
		for (int j=0;j<5;j++)// 0 and the result.
		{
			population[i].alleles[j] = rand() % 2;
			cout<<population[i].alleles[j];
		}
		cout<<endl;
	}
	if (fitness = CreateFitnesses()) 
	{
		return fitness;
	}
	int iterations = 0;// Вести учет итераций.
	while (fitness != 0 || iterations < 50)// Повторяйте, пока решение не найдено, или более 50 итераций.
	{
		GenerateLikelihoods();// Create the likelihoods.
		CreateNewPopulation();
		if (fitness = CreateFitnesses()) 
		{
			return fitness;
		}
		iterations++;
	}
	return -1;
}

int CDiophantine::Fitness(gene &gn)
{
	int total = ca * gn.alleles[0] + cb * gn.alleles[1] + cc * gn.alleles[2] + cd * gn.alleles[3]+ ce * gn.alleles[4];

	return gn.fitness = abs(total - result);
}

int CDiophantine::CreateFitnesses() 
{
	float avgfit = 0;
	int fitness = 0;
	for(int i=0;i<MAXPOP;i++) {
		fitness = Fitness(population[i]);
		avgfit += fitness;
		if (fitness == 0) {
			return i;
		}
	}
	return 0;
}
float CDiophantine::MultInv()
{
	float sum = 0;

	for(int i=0;i<MAXPOP;i++) {
		sum += 1/((float)population[i].fitness);
	}

	return sum;
}

void CDiophantine::GenerateLikelihoods() 
{
	float multinv = MultInv();

	float last = 0;
	for(int i=0;i<MAXPOP;i++) {
		population[i].likelihood = last = last + ((1/((float)population[i].fitness) / multinv) * 100);
	}
}
int CDiophantine::GetIndex(float val) {
	float last = 0;
	for(int i=0;i<MAXPOP;i++) {
		if (last <= val && val <= population[i].likelihood) return i;
		else last = population[i].likelihood;
	}
	
	return 5;
}
gene CDiophantine::Breed(int p1, int p2)
{
	int crossover = rand() % 4+1;// Создать точку пересечения (не первый).
	int first = rand() % 100;// Кто из родителей на первом месте?

	gene child = population[p1];// Child is all first parent initially.Ребенок все первый родитель на начальном этапе.

	int initial = 0, final = 4;// Кроссовер границ.
	if (first < 50) initial = crossover;	// If first parent first. start from crossover.  Если первый родитель в первую очередь. начать с кроссовером.
	else final = crossover+1;// Else end at crossover.

	for(int i=initial;i<final;i++)
	{// Crossover!
		child.alleles[i] = population[p2].alleles[i];
		if (rand() % 101 < 6) child.alleles[i] = rand() % (result + 1);
	}

	return child;// Return the kid...
}

void CDiophantine::CreateNewPopulation()
{
	gene temppop[MAXPOP];

	for(int i=0;i<MAXPOP;i++) 
	{
		int parent1 = 0, parent2 = 0, iterations = 0;
		while(parent1 == parent2 || population[parent1] == population[parent2])
		{
			parent1 = GetIndex((float)(rand() % 101));
			parent2 = GetIndex((float)(rand() % 101));
			if (++iterations > 25) break;
		}
	temppop[i] = Breed(parent1, parent2);// Create a child.
	}

	for(int i=0;i<MAXPOP;i++) population[i] = temppop[i];
}
void main() 
{
	setlocale(LC_ALL,"russian");
	ifstream ifst("input.txt");
	predmet A[100];
	int g,ans,P=0,n=0,m=0,W=0;
	int *a = new int[m]; //массив содержащий веса
	int *b = new int[n];
	for(;!ifst.eof();){A[m].In(ifst);m++;}
	for (int i=0;i<m;i++) a[i]=A[i].get_w();
	
	cout<<" Введите вес рюкзака:"<<endl;cin>>g;
	cout<<"\t** Полученные хромосомы:"<<endl;
   CDiophantine dp(a[0],a[1],a[2],a[3],a[4],g);
   ans = dp.Solve();
   if (ans == -1) 
   {
      cout << "No solution found." << endl;
   }
   else 
   {
	  cout << "\t** Вес рюкзака равен "<<g<<" **"<<endl;
	  cout << "\n Все предметы: \n"<<endl;
	  ifstream ifst("input.txt");
	  for(;!ifst.eof();)
	  {
	    	A[n].In(ifst);
	    	A[n].prin();
		    n++;
	  }
      gene gn = dp.GetGene(ans);
	  cout << "\n\t*** Наилучшая хромосома: ";
      cout << "( "<<gn.alleles[0] << " . ";
      cout << gn.alleles[1] << " . ";
      cout << gn.alleles[2] << " . ";
      cout << gn.alleles[3] << " . ";
      cout << gn.alleles[4] << " ) ***" << endl;
	  for(int i=0;i<5;i++) b[i]=gn.alleles[i];
	  cout<<"\n В рюкзаке присутствуют:\n\n";
	  print(b);
	  for (int i=0;i<n;i++) P+=A[i].get_p()*gn.alleles[i];
	  cout<<"\n\t** Стоимость рюкзака равна "<<P<<" **"<<endl;
	   cin.get();
	   cin.get();

   }
}
Yandex
Объявления
19.02.2014, 15:39     Задача о ранце
Ответ Создать тему
Опции темы

Текущее время: 09:07. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru