| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
典型的多重背包问题// 以下两种方法均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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator