HDU 2844 Coins——多重背包

HDU 2844 Coins——多重背包

套用多重背包模板，如果发现这个代码在POJ 1742上超时

#include #include #include #include using namespace std;const int maxn = 100000 + 10;int N, V, amount[maxn], capacity[maxn], weight[maxn];int dp[maxn];void bag01(int cost, int weight) { for (int i = V; i >= cost; i--) { dp[i] = max(dp[i], dp[i - cost] + weight); }}void completebag(int cost, int weight) { for (int i = cost; i <= V; i++) { dp[i] = max(dp[i], dp[i - cost] + weight); }}void multiplybag(int cost, int weight, int amount) { if (cost * amount >= V) completebag(cost, weight); else { int k = 1; while (k < amount) { bag01(k * cost, k * weight); amount -= k; k += k; } bag01(amount * cost, amount * weight); }}int main(){ while (scanf("%d %d", &N, &V) == 2 && N + V) { memset(dp, 0, sizeof(dp)); for (int i = 1; i <= N; i++) scanf("%d", &capacity[i]); for (int i = 1; i <= N; i++) scanf("%d", &amount[i]); for (int i = 1; i <= N; i++) { multiplybag(capacity[i], capacity[i], amount[i]); } int ans = 0; for (int i = 1; i <= V; i++) { if (dp[i] == i) ans++; } printf("%d\n", ans); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。