HDU 1114 Piggy-Bank——完全背包

HDU 1114 Piggy-Bank——完全背包

O(VN)的完全背包，注意题目限制条件：物品总cost恰好达到V，一开始还优化了一下， 把val小cost大的物品去掉了，后来一想这样会产生错误的结果

#include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int MAXN = 500 + 10;const int MAXV = 10000 + 10;int T, N, V, dp[MAXV];struct Item { int val, cost;}item[MAXN];int main() { scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { int a, b; scanf("%d %d", &a, &b); V = b - a; scanf("%d", &N); for (int i = 1; i <= N; i++) { scanf("%d %d", &item[i].val, &item[i].cost); } for (int i = 1; i <= V; i++) dp[i] = INF; for (int i = 1; i <= N; i++) { for (int j = item[i].cost; j <= V; j++) { dp[j] = min(dp[j], dp[j - item[i].cost] + item[i].val); } } if (dp[V] == INF) printf("This is impossible.\n"); else { printf("The minimum amount of money in the piggy-bank is %d.\n", dp[V]); } } return 0;}

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