HDOJ(HDU).1114 Piggy-Bank (DP 完全背包)

2019-11-08 01:50:59

字体：大中小

来源：转载

供稿：网友

HDOJ(HDU).1114 Piggy-Bank (DP 完全背包)

题意分析

裸的完全背包

代码总览

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define nmax 100000#define INF 0x3f3f3f3fusing namespace std;int we[nmax],va[nmax],dp[nmax];struct item{ int w; int v;}arr[nmax];int main(){ //freopen("in.txt","r",stdin); int t; scanf("%d",&t); while(t--){ int e,f; scanf("%d%d",&e,&f); int n; scanf("%d",&n); memset(arr,0,sizeof(arr)); memset(dp,INF,sizeof(dp)); for(int i =1; i<=n; ++i){ scanf("%d%d",&arr[i].v,&arr[i].w); } dp[0] = 0; for(int i =1 ;i<=n; ++i){ for(int j = arr[i].w; j<=(f-e);++j) dp[j] = min(dp[j],dp[j-arr[i].w]+arr[i].v); } if(dp[f-e] == INF) PRintf("This is impossible./n"); else printf("The minimum amount of money in the piggy-bank is %d./n",dp[f-e]); } return 0;}

上一篇：在SSM中使用shiro实现登录验证（附密码加密）

下一篇：Advanced Techniques for Mobile Robotic