首页 > 代码库 > poj-1384 Piggy-Bank
poj-1384 Piggy-Bank
poj-1384 Piggy-Bank 地址：http://poj.org/problem?id=1384
题意：
知道盒子里面的物体的总重量，得到每一种硬币的价格和重量，求最少钱构成盒子物体总重量的钱的数量。
分析：
典型的不限重背包问题。当然维度也是在可以接受的范围， 直接设置dp数组进行min操作。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> using namespace std; const int maxn = 505; const int max_val = 10000; int E,F, n, dp[max_val+5]; struct Node{ int p,w; }nd[maxn]; int cmp(const void* a, const void* b){ Node* aa = (Node *)a; Node* bb = (Node *)b; return (bb->w*1.0)/(bb->p*1.0) - (aa->w*1.0)/(aa->p*1.0); }int main(){ freopen("in.txt", "r", stdin); int test_num, i, j; scanf("%d", &test_num); while(test_num--){ scanf("%d %d", &E, &F); scanf("%d", &n); for(i=0; i<n; i++){ scanf("%d %d", &nd[i].p, &nd[i].w); } memset(dp, 0x3f3f3f3f, sizeof(dp)); dp[0] = 0; for(i=0; i<n; i++){ for(j=nd[i].w; j<=(F-E); j++){ if(dp[j - nd[i].w] != 0x3f3f3f3f ){ dp[j] = min(dp[j-nd[i].w]+nd[i].p, dp[j]); } } } if(dp[F-E] == 0x3f3f3f3f){ printf("This is impossible.\n"); }else{ printf("The minimum amount of money in the piggy-bank is %d.\n", dp[F-E]); } } return 0; }
poj-1384 Piggy-Bank
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。