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