本文主要是介绍POJ 1742 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题是多重背包问题。我用的简单的二进制优化。主要是看到discuss里面这样就过了，也没去考虑别的优化。
代码基本上重用的POJ1276:http://blog.csdn.net/thestoryofsnow/article/details/41939829。
关于dp的类型，我本来用的是int，然后看dp[i] == i。这样超时了，看了discuss里面用bool，即dp[V] |= dp[V - cost]。这样就通过了。
| thestoryofsnow | 1742 | Accepted | 228K | 2329MS | C++ | 1589B |
/*
ID: thestor1
LANG: C++
TASK: poj1742
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>using namespace std;const int MAXN = 100;
const int MAXCASH = 100000;void zeroPack(int cost, bool dp[], const int cash)
{// zeroPackfor (int V = cash; V >= cost; --V){dp[V] |= dp[V - cost];}
}void completePack(int cost, bool dp[], const int cash)
{for (int V = cost; V <= cash; ++V){dp[V] |= dp[V - cost];}
}void multiplePack(int cnt, int cost, bool dp[], int cash)
{if (cnt * cost >= cash){// completePack// no constraints on item's 'cnt'completePack(cost, dp, cash);}else{// transform to finite items and applies zeroPackint k = 1;while (k < cnt){zeroPack(k * cost, dp, cash);cnt -= k;k <<= 1;}zeroPack(cnt * cost, dp, cash);}
}int main()
{ int cnt[MAXN], cost[MAXN];bool dp[MAXCASH + 1];dp[0] = true;int n, m;while (scanf("%d%d", &n, &m) && !(n == 0 && m == 0)){for (int i = 0; i < n; ++i){scanf("%d", &cost[i]);}for (int i = 0; i < n; ++i){scanf("%d", &cnt[i]);}memset(dp + 1, false, m * sizeof(bool));for (int i = 0; i < n; ++i){multiplePack(cnt[i], cost[i], dp, m);}printf("%ld\n", count(dp + 1, dp + m + 1, true));}return 0;
}这篇关于POJ 1742 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
