poj-1384 Piggy-Bank

时间:2022-01-03 20:52:12

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 = ;
const int max_val = ; int E,F, n, dp[max_val+]; 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=; i<n; i++){
scanf("%d %d", &nd[i].p, &nd[i].w);
}
memset(dp, 0x3f3f3f3f, sizeof(dp));
dp[] = ;
for(i=; 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 ;
}