Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

典型的多重背包问题

Posted by zoujing1978 at 2017-04-08 11:09:53 on Problem 1014
// 以下两种方法均AC了

//#define  _CRT_SECURE_NO_WARNINGS
//
//#include <iostream>
//#include <cstdio>
//#include <deque>
//#include <algorithm>
//using namespace std;
//
//template <typename T>
//T MulityKnapsack(int *w, T* v, int* t, int N, int W, T* f)
//{
//	memset(f, 0, sizeof(T)*(W + 1));
//	for (int i = 0; i < N; i++)
//	{
//		int m = ((w[i] == 0) ? t[i] : min(t[i], W / w[i]));
//		deque<T> q1; // 存储状态的队列
//		deque<T> q2; // 单调队列
//		for (int b = 0; b < w[i]; b++)
//		{
//			int c = 0;
//			for (int k = b; k <= W; k += w[i])
//			{
//				if (q1.size() == m + 1)
//				{
//					if (q2.front() == q1.front())
//					{
//						q2.pop_front();
//					}
//					q1.pop_front();
//				}
//				double temp = f[k] - c * v[i];
//				q1.push_back(temp);
//				while (q2.size() > 0 && q2.back() < temp)
//				{
//					q2.pop_back();
//				}
//				q2.push_back(temp);
//				f[k] = q2.front() + c * v[i];
//				++c;
//			}
//		}
//	}
//	return f[W];
//}
//
//int main()
//{
//	const int n = 6;
//	int num[n];
//	int w[n];
//	int caseIndex = 0;
//	while (true)
//	{
//		int weight = 0;
//		for (int i = 0; i < n; i++)
//		{
//			scanf("%d", &num[i]);
//			w[i] = i + 1;
//			weight += w[i] * num[i];
//		}
//		if (weight == 0)
//		{
//			break;
//		}
//		printf("Collection #%d:\n", ++caseIndex);
//		if ((weight & 1) != 0)
//		{
//			printf("Can't be divided.\n\n");
//			continue;
//		}
//		int mid = weight >> 1;
//		int* f = new int[mid + 1];
//		MulityKnapsack(w, w, num, n, mid, f);
//		if (f[mid] == mid)
//		{
//			printf("Can be divided.\n\n");
//		}
//		else
//		{
//			printf("Can't be divided.\n\n");
//		}
//		delete[] f;
//	}
//	return 0;
//}

#define  _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

template <typename T>
T knap_op(T* f, int* w, T* v, int W, int n) //动态规划法求0/1背包问题的空间优化算法
{
	for (int r = 0; r <= W; r++)
	{
		f[r] = 0; //置边界条件
	}
	for (int i = 0; i < n; i++)
	{
		for (int r = W; r >= w[i]; r--)
		{
			f[r] = max(f[r], f[r - w[i]] + v[i]);
		}
	}
	return f[W];		//返回总价值
}

template <typename T>
T MulityKnapsack(int *w, T* v, int* t, int n, int W, T* f)
{
	int m = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = t[i]; j > 0; j /= 2)
		{
			m++;
		}
	}
	m++;
	int* ww = new int[m];
	int* vv = new T[m];
	m = 0;
	for (int i = 0; i < n; i++)
	{
		int k = 0;
		for (int j = 0; (1 << j) < t[i]; j++)
		{
			ww[m] = (1 << j) * w[i];
			vv[m] = (1 << j) * v[i];
			k += (1 << j);
			m++;
		}
		if (t[i] > k)
		{
			ww[m] = (t[i] - k) * w[i];
			vv[m] = (t[i] - k) * v[i];
			m++;
		}
	}
	knap_op(f, ww, vv, W, m);
	delete[] vv;
	delete[] ww;
	return f[W];
}

int main()
{
	//freopen("Text.txt", "r", stdin);
	const int n = 6;
	int t[n];
	int w[n];
	int caseIndex = 0;
	while (true)
	{
		int m = 0;
		int weight = 0;
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &t[i]);
			w[i] = i + 1;
			weight += w[i] * t[i];
		}
		if (weight == 0)
		{
			break;
		}
		printf("Collection #%d:\n", ++caseIndex);
		if ((weight & 1) != 0)
		{
			printf("Can't be divided.\n\n");
			continue;
		}
		int mid = weight >> 1;
		int* f = new int[mid + 1];
		MulityKnapsack(w, w, t, n, mid, f);
		if (f[mid] == mid)
		{
			printf("Can be divided.\n\n");
		}
		else
		{
			printf("Can't be divided.\n\n");
		}
		delete[] f;
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator