Задача на С++. формирование выбора предметов - Помощь студентам

Veina · 12.12.2009, 16:16

Задача на С++. Формирование набора предметов. В текстовом файле записаны названия некоторых предметов, а так же их веса и ценности. При заданном ограничении на суммарный вес предметов, сформировать набор, имеющий наибольшую совокупную ценность.
Например:
задается:
мишка_0,3кг_200р.
молоко_0,1кг_20р.
диван_12кг_5000р.
стул_2кг_2000р.
кресло_9кг_4000р.
парта_7кг_1500р.
монитор_20кг_25000р.
холодильник_20кг_25000кг.
телевизор_17кг_13000р.

задается вес не более 50 кг, т. е. сформировать набор не более, чем на 50 кг. из предметов наибольшей ценности.
результат должен быть таким:
холодильник_20кг_25000р.
монитор_4кг_15000р.
телевизор_17кг_13000р.
итог: 41кг_53000р.

помогите, пожалуйста. очень нужна эта задача.

Alex_FF · 17.12.2009, 00:23

решение (Код исправлен):

Код:

#include <iostream>
#include <fstream>

using namespace std;

bool x[51];

int knapsack1_0(const int wts[50], const int cost[50], const int n, const int W)
{
	int i, k;
	int dp[5001][51];
	for (i = 0; i <= W; i++)
		dp[i][0] = 0;
	for (i = 0; i <= n; i++)
		dp[0][i] = 0;
	for (int j = 1; j <= n; j++)
		for (int w = 1; w <= W; w++)
			if (wts[j - 1] <= w)
				dp[w][j] = max(dp[w][j - 1], dp[w - wts[j - 1]][j - 1] + cost[j - 1]);
			else
				dp[w][j] = dp[w][j - 1];
	i = W;
	k = n;
	while ((i > 0) && (k > 0))
		if (dp[i][k] != dp[i][k - 1])
		{
			x[k - 1] = true;
			k--;
			i -= wts[k];
		}
		else k--;

	return dp[W][n];
}

int main()
{
	ifstream fi;
	ofstream fo;
	char nm[50][100];
	int wts[50], cost[50];
	int i, z, h = 0, t = 0, k = 0, W;
	float M;
	for (i = 0; i < 51; i++)
		x[i] = false;
	fi.open("input.txt");
	fo.open("output.txt");
	while (!fi.eof())
	{
		char tmp[100];
		fi >> nm[k];
		for (i = 0; i < strlen(nm[k]); i++)
			if (nm[k][i] == '_') break;
		i++;
		z = 0;
		for (int j = 0; j < 100; j++)
			tmp[j] = '\0';
		while (nm[k][i] != 'к')
		{
			if (nm[k][i] != ',') tmp[z++] = nm[k][i];
			else tmp[z++] = '.';
			i++;
		}
		wts[h++] = atof(tmp) * 100 + 0.001;
		i = i + 3;
		z = 0;
		for (int j = 0; j < 100; j++)
			tmp[j] = '\0';
		while (nm[k][i] != 'р')
			tmp[z++] = nm[k][i++];
		cost[t++] = atoi(tmp);
		k++;
	}
	cout << "Enter max. weight\n" ;
	cin >> M;
	W = M * 100 + 0.001;
	int sum1 = knapsack1_0(wts, cost, k, W);
	for (i = 0; i < 51; i++)
		if (x[i]) fo << nm[i] << endl;
	float sum2 = 0;
	for (i = 0; i < k; i++)
		if (x[i]) sum2 += wts[i];
	fo.precision(4);
	fo << "итог: " << sum2 / 100 <<"кг_" << sum1 << "р.";
	return 0;
}

Пример (макс. вес задавался = 50):

вход:

мишка_0,3кг_200р.
молоко_0,1кг_20р.
диван_12кг_5000р.
стул_2кг_2000р.
кресло_9кг_4000р.
парта_7кг_1500р.
монитор_20кг_25000р.
холодильник_20кг_25000р.
телевизор_17кг_13000р.

выход:

мишка_0,3кг_200р.
молоко_0,1кг_20р.
кресло_9кг_4000р.
монитор_20кг_25000р.
холодильник_20кг_25000р.
итог: 49.4кг_54220р.

//////////////////////////////////////////////////
В примерах которые вы привели, содержаться ошибки:
1) стоимость холодильника в кг, вместо р.
2) на входе монитор весит 20 кг, а на выходе почему-то 4.
Следовательно, ваши примеры неправильны. Правильные примеры я привел выше.

В моём решении, макс. вес вводится с клавиатуры.
Максимальное количество товаров на входе - 50.
Общий вес, указывающийся в конце выходного файла записывается с десятичной точкой, если число дробное. Если нужна запятая, то можете переделать....
Всё, что содержится во входном файле должно строго соответствовать формату: НАИМЕНОВАНИЕ_ВЕСкг_СТОИМОСТЬр.
Регистр в наименовании значения не имеет, но "кг" и "р." должны быть в нижнем регистре. Разделитель целой и дробной части на входе - запятая. Максимальное количество цифр после запятой - 2 (как было обговорено).

Veina · 17.12.2009, 08:18

так в выходящем файле все правильно, только еще один вопрос: когда запускаю программу, окно появляется и сразу исчезает с ошибкой:
'pz.exe': Loaded 'C:\WINDOWS\system32\kernel32.dll'
AVRF: verifier.dll provider initialized for pz.exe with flags 0x40007
'pz.exe': Loaded 'C:\WINDOWS\WinSxS\x86_Microsoft.VC 90.DebugCRT_1fc8b3b9a1e18e3b_9.0.21 022.8_x-ww_597c3456\msvcp90d.dll', Symbols loaded.
'pz.exe': Loaded 'C:\WINDOWS\WinSxS\x86_Microsoft.VC 90.DebugCRT_1fc8b3b9a1e18e3b_9.0.21 022.8_x-ww_597c3456\msvcr90d.dll', Symbols loaded.
The program '[200] pz.exe: Native' has exited with code 0 (0x0).

и еще как я поняла вес там уже стоит как бы по умолчанию не более 50 кг., а мне нужно чтобы я сама его вводила.
заранее спасибо

Alex_FF · 17.12.2009, 09:08

Цитата:

мишка_0,3кг_200р.
молоко_0,1кг_20р.
диван_12кг_5000р.
стул_2кг_2000р.
кресло_9кг_4000р.
парта_7кг_1500р.
монитор_20кг_25000р.
холодильник_20кг_25000кг.
телевизор_17кг_13000р.

Цитата:

результат должен быть таким:
холодильник_20кг_25000р.
монитор_4кг_15000р.
телевизор_17кг_13000р.
итог: 41кг_53000р.

во входном файле у вас монитор 20 кг весит, а в выходном - 4 кг, и стоимость у монитора разная на входе и выходе. В этой задаче вес у предметов фиксированный, т. е. его менять нельзя (да и нет смысла). Так что, ваш пример неправильный!
Вес вводится с клавиатуры (исправил).
А насчет ошибки не знаю, у меня на RAD Studio 2009 все работает нормально, а вот в Visual Studio 2008 выдаёт ошибку при исполнении, хотя компилируется нормально. Это можно избежать запустив сам скомпилированный exe файл, а не нажимая F5, в Visual Studio.
Так что, компилируйте вначале, а потом запускайте exe файл.

Кстати, если во входном файле заменить вес монитора и его стоимость на ту, которая у вас на выходном указана, и ввести ограничение на вес в 41 кг., то выход будет таким:

монитор_4кг_15000р.
холодильник_20кг_25000р.
телевизор_17кг_13000р.
итог: 41кг_53000р.

Так, что исправьте в вашем примере во входном файле ошибки: во-первых, стоимость телевизора всё-таки в рублях, а не килограммах, и, во-вторых, вес и стоимость монитора.

Цитата:

так в выходящем файле все правильно

это видели? :

Цитата:

//////////////////////////////////////////////////
В примерах которые вы привели, содержаться ошибки:
1) стоимость холодильника в кг, вместо р.
2) на входе монитор весит 20 кг, а на выходе почему-то 4.
Следовательно, ваши примеры неправильны. Правильные примеры я привел выше.

Советую все-таки читать, что вам пишут и хоть немного анализировать это, а не спорить, что вот у вас всё правильно, и что 20 = 4 и 25000 = 15000

Alex_FF · 17.12.2009, 14:13

это хорошо, что я на RAD Studio писал, а не на VS, а то пришлось бы искать ошибку, которой на самом деле нет...

Veina · 17.12.2009, 14:24

Цитата:

Сообщение от Alex_FF

во входном файле у вас монитор 20 кг весит, а в выходном - 4 кг, и стоимость у монитора разная на входе и выходе. В этой задаче вес у предметов фиксированный, т. е. его менять нельзя (да и нет смысла). Так что, ваш пример неправильный!
Вес вводится с клавиатуры (исправил).
А насчет ошибки не знаю, у меня на RAD Studio 2009 все работает нормально, а вот в Visual Studio 2008 выдаёт ошибку при исполнении, хотя компилируется нормально. Это можно избежать запустив сам скомпилированный exe файл, а не нажимая F5, в Visual Studio.
Так что, компилируйте вначале, а потом запускайте exe файл.

Кстати, если во входном файле заменить вес монитора и его стоимость на ту, которая у вас на выходном указана, и ввести ограничение на вес в 41 кг., то выход будет таким:

монитор_4кг_15000р.
холодильник_20кг_25000р.
телевизор_17кг_13000р.
итог: 41кг_53000р.

Так, что исправьте в вашем примере во входном файле ошибки: во-первых, стоимость телевизора всё-таки в рублях, а не килограммах, и, во-вторых, вес и стоимость монитора.

это видели? :

Советую все-таки читать, что вам пишут и хоть немного анализировать это, а не спорить, что вот у вас всё правильно, и что 20 = 4 и 25000 = 15000

да я и не спорила,да, увидела что сделала опечатку в примерах. а когда говорила, что в выходном файле все правильно, я просто имела ввиду, что все нормально. программа работает, только ввод хотела с клавы. вот и все

Alex_FF · 17.12.2009, 20:44

ну я подумал, что вы утверждаете, что ваши примеры правильные

Так всё правильно решено, или что-то еще нужно переделать?

Veina · 18.12.2009, 16:00

все правильно. работает, спасибо огромное. просто если я допустим захочу поставить максимальный вес не 50, а допустим 100, просто везде заменить 50 на 100?

Alex_FF · 18.12.2009, 17:40

Цитата:

Сообщение от Veina

все правильно. работает, спасибо огромное. просто если я допустим захочу поставить максимальный вес не 50, а допустим 100, просто везде заменить 50 на 100?

я использовал алгоритм для задачи, в которой вес является целым числом. В вашей задаче вес - дробное число, с двумя знаками после запятой, поэтому я просто домножал вес на 100. Из-за этого массив dp пришлось увеличить также в 100 раз. Это дополнительный расход памяти, и времени выполнения.
Чтобы вводить вес 100 кг нужно массив dp[5001][51] описать как dp[10001][51]. Больше ничего менять не надо.
Массив wts[50] - массив весов, здесь 50 - это максимальное количество предметов, которое может быть во входном файле, аналогично для массива стоимостей cost[50] - здесь 50 - это кол-во предметов. Массив x[51] используется для определения, какой из предметов надо включать в выходной файл, а какой нет. 51 - это кол-во предметов + еще единица. Массив nm[50][100] представляет собой массив строк, считанных из входного файла, здесь 50 - это кол-во предметов, 100 - длина строки.
Так что число 50 здесь к весу отношения никакого не имеет
За вес отвечает массив dp, а точнее его первое измерение. Если будете его менять, не забывайте, что его измерения должны быть всегда на единицу больше, чем вес и кол-во предметов.
К тому же просто увеличив dp[5001][51] до dp[10001][51] программа у вас работать не будет

, так как будет переполнение стека. Нужно увеличить размер стека, но как это делается в Visual Studio я не знаю, ибо использую RAD Studio. Спросите, например, у препода, может он вам скажет...

Alex_FF · 23.12.2009, 00:39

вот решение, которое работает для любого веса.
количество предметов во входном файле задается константой Q.

Код:

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int Q = 100;

bool x[Q + 1];

int knapsack1_0(vector<int>& wts, vector<int>& cost, const int n, const int W)
{
	vector<vector<int> > dp(W + 1);
	for (int i = 0; i <= W; i++)
	{
		dp[i].resize(n + 1);
		dp[i][0] = 0;
	}
	for (size_t i = 0; i <= n; i++)
		dp[0][i] = 0;
	for (size_t j = 1; j <= n; j++)
		for (int w = 1; w <= W; w++)
			if (wts[j - 1] <= w)
				dp[w][j] = max(dp[w][j - 1], dp[w - wts[j - 1]][j - 1] + cost[j - 1]);
			else
				dp[w][j] = dp[w][j - 1];
	size_t i = W;
	size_t k = n;
	while ((i > 0) && (k > 0))
		if (dp[i][k] != dp[i][k - 1])
		{
			x[k - 1] = true;
			k--;
			i -= wts[k];
		}
		else k--;

	return dp[W][n];
}

int main()
{
	ifstream fi;
	ofstream fo;
	char nm[Q][100];
	vector<int> wts;
	vector<int> cost;
	size_t i, z, h = 0, t = 0, k = 0, W;
	float M;
	for (i = 0; i < Q + 1; i++)
		x[i] = false;
	fi.open("input.txt");
	fo.open("output.txt");
	while (!fi.eof())
	{
		char tmp[100];
		fi >> nm[k];
		for (i = 0; i < strlen(nm[k]); i++)
			if (nm[k][i] == '_') break;
		i++;
		z = 0;
		for (int j = 0; j < 100; j++)
			tmp[j] = '\0';
		while (nm[k][i] != 'к')
		{
			if (nm[k][i] != ',') tmp[z++] = nm[k][i];
			else tmp[z++] = '.';
			i++;
		}
		wts.resize(k + 1);
		wts[h++] = atof(tmp) * 100 + 0.001;
		i = i + 3;
		z = 0;
		for (int j = 0; j < 100; j++)
			tmp[j] = '\0';
		while (nm[k][i] != 'р')
			tmp[z++] = nm[k][i++];
		cost.resize(k + 1);
		cost[t++] = atoi(tmp);
		k++;
	}
	cout << "Enter max. weight\n" ;
	cin >> M;
	W = M * 100 + 0.001;
	int sum1 = knapsack1_0(wts, cost, k, W);
	for (i = 0; i < Q + 1; i++)
		if (x[i]) fo << nm[i] << endl;
	float sum2 = 0;
	for (i = 0; i < k; i++)
		if (x[i]) sum2 += wts[i];
	fo.precision(4);
	fo << "итог: " << sum2 / 100 <<"кг_" << sum1 << "р.";
	return 0;
}

12.12.2009, 16:16	#1
Veina Пользователь Регистрация: 28.10.2009 Сообщений: 34	Задача на С++. формирование выбора предметов Задача на С++. Формирование набора предметов. В текстовом файле записаны названия некоторых предметов, а так же их веса и ценности. При заданном ограничении на суммарный вес предметов, сформировать набор, имеющий наибольшую совокупную ценность. Например: задается: мишка_0,3кг_200р. молоко_0,1кг_20р. диван_12кг_5000р. стул_2кг_2000р. кресло_9кг_4000р. парта_7кг_1500р. монитор_20кг_25000р. холодильник_20кг_25000кг. телевизор_17кг_13000р. задается вес не более 50 кг, т. е. сформировать набор не более, чем на 50 кг. из предметов наибольшей ценности. результат должен быть таким: холодильник_20кг_25000р. монитор_4кг_15000р. телевизор_17кг_13000р. итог: 41кг_53000р. помогите, пожалуйста. очень нужна эта задача.

17.12.2009, 00:23	#2
Alex_FF Удален Форумчанин Регистрация: 02.12.2009 Сообщений: 309	решение решение (Код исправлен): Код: #include <iostream> #include <fstream> using namespace std; bool x[51]; int knapsack1_0(const int wts[50], const int cost[50], const int n, const int W) { int i, k; int dp[5001][51]; for (i = 0; i <= W; i++) dp[i][0] = 0; for (i = 0; i <= n; i++) dp[0][i] = 0; for (int j = 1; j <= n; j++) for (int w = 1; w <= W; w++) if (wts[j - 1] <= w) dp[w][j] = max(dp[w][j - 1], dp[w - wts[j - 1]][j - 1] + cost[j - 1]); else dp[w][j] = dp[w][j - 1]; i = W; k = n; while ((i > 0) && (k > 0)) if (dp[i][k] != dp[i][k - 1]) { x[k - 1] = true; k--; i -= wts[k]; } else k--; return dp[W][n]; } int main() { ifstream fi; ofstream fo; char nm[50][100]; int wts[50], cost[50]; int i, z, h = 0, t = 0, k = 0, W; float M; for (i = 0; i < 51; i++) x[i] = false; fi.open("input.txt"); fo.open("output.txt"); while (!fi.eof()) { char tmp[100]; fi >> nm[k]; for (i = 0; i < strlen(nm[k]); i++) if (nm[k][i] == '_') break; i++; z = 0; for (int j = 0; j < 100; j++) tmp[j] = '\0'; while (nm[k][i] != 'к') { if (nm[k][i] != ',') tmp[z++] = nm[k][i]; else tmp[z++] = '.'; i++; } wts[h++] = atof(tmp) * 100 + 0.001; i = i + 3; z = 0; for (int j = 0; j < 100; j++) tmp[j] = '\0'; while (nm[k][i] != 'р') tmp[z++] = nm[k][i++]; cost[t++] = atoi(tmp); k++; } cout << "Enter max. weight\n" ; cin >> M; W = M * 100 + 0.001; int sum1 = knapsack1_0(wts, cost, k, W); for (i = 0; i < 51; i++) if (x[i]) fo << nm[i] << endl; float sum2 = 0; for (i = 0; i < k; i++) if (x[i]) sum2 += wts[i]; fo.precision(4); fo << "итог: " << sum2 / 100 <<"кг_" << sum1 << "р."; return 0; } Пример (макс. вес задавался = 50): вход: мишка_0,3кг_200р. молоко_0,1кг_20р. диван_12кг_5000р. стул_2кг_2000р. кресло_9кг_4000р. парта_7кг_1500р. монитор_20кг_25000р. холодильник_20кг_25000р. телевизор_17кг_13000р. выход: мишка_0,3кг_200р. молоко_0,1кг_20р. кресло_9кг_4000р. монитор_20кг_25000р. холодильник_20кг_25000р. итог: 49.4кг_54220р. ////////////////////////////////////////////////// В примерах которые вы привели, содержаться ошибки: 1) стоимость холодильника в кг, вместо р. 2) на входе монитор весит 20 кг, а на выходе почему-то 4. Следовательно, ваши примеры неправильны. Правильные примеры я привел выше. В моём решении, макс. вес вводится с клавиатуры. Максимальное количество товаров на входе - 50. Общий вес, указывающийся в конце выходного файла записывается с десятичной точкой, если число дробное. Если нужна запятая, то можете переделать.... Всё, что содержится во входном файле должно строго соответствовать формату: НАИМЕНОВАНИЕ_ВЕСкг_СТОИМОСТЬр. Регистр в наименовании значения не имеет, но "кг" и "р." должны быть в нижнем регистре. Разделитель целой и дробной части на входе - запятая. Максимальное количество цифр после запятой - 2 (как было обговорено). Последний раз редактировалось Alex_FF; 17.12.2009 в 12:17.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Оператор выбора	Largo	Помощь студентам	11	28.03.2009 19:19
задача на формирование массива. паскаль	Ananim-Pbl6ak	Помощь студентам	8	20.03.2009 03:57
Формирование остатков	RUBEY	Microsoft Office Excel	2	24.01.2008 19:32
Оператор выбора...	Bill Gates	Общие вопросы Delphi	3	22.01.2008 11:32

17.12.2009, 08:18	#3
Veina Пользователь Регистрация: 28.10.2009 Сообщений: 34	так в выходящем файле все правильно, только еще один вопрос: когда запускаю программу, окно появляется и сразу исчезает с ошибкой: 'pz.exe': Loaded 'C:\WINDOWS\system32\kernel32.dll' AVRF: verifier.dll provider initialized for pz.exe with flags 0x40007 'pz.exe': Loaded 'C:\WINDOWS\WinSxS\x86_Microsoft.VC 90.DebugCRT_1fc8b3b9a1e18e3b_9.0.21 022.8_x-ww_597c3456\msvcp90d.dll', Symbols loaded. 'pz.exe': Loaded 'C:\WINDOWS\WinSxS\x86_Microsoft.VC 90.DebugCRT_1fc8b3b9a1e18e3b_9.0.21 022.8_x-ww_597c3456\msvcr90d.dll', Symbols loaded. The program '[200] pz.exe: Native' has exited with code 0 (0x0). и еще как я поняла вес там уже стоит как бы по умолчанию не более 50 кг., а мне нужно чтобы я сама его вводила. заранее спасибо

17.12.2009, 14:13	#5
Alex_FF Удален Форумчанин Регистрация: 02.12.2009 Сообщений: 309	это хорошо, что я на RAD Studio писал, а не на VS, а то пришлось бы искать ошибку, которой на самом деле нет...

17.12.2009, 20:44	#7
Alex_FF Удален Форумчанин Регистрация: 02.12.2009 Сообщений: 309	ну я подумал, что вы утверждаете, что ваши примеры правильные Так всё правильно решено, или что-то еще нужно переделать?

18.12.2009, 16:00	#8
Veina Пользователь Регистрация: 28.10.2009 Сообщений: 34	все правильно. работает, спасибо огромное. просто если я допустим захочу поставить максимальный вес не 50, а допустим 100, просто везде заменить 50 на 100?