HDOJ1114解题报告【完全背包】

题目地址：

　　http://acm.hdu.edu.cn/showproblem.php?pid=1114

题目概述：

　　这个题的难度估计就是在读题上了……

　　给出n组{p，w}，其中p为价值，w为重量，再给出一个容器的容积，请填满容器并使总价值最小，每组都可以重复使用。

大致思路：

　　看了题目概述之后是不是瞬间懂了，很显然的完全背包嘛。

　　dp[i]表示容积为i时最小的价值，转移方程是：dp[i]=min(dp[i],dp[i-w]+p)

　　初始化为inf，dp[0]=0。

代码：

1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <vector> 6 #include <ctime> 7 #include <map> 8 #include <stack> 9 #include <queue> 10 #include <cstring> 11 #include <algorithm> 12 using namespace std; 13 14 #define sacnf scanf 15 #define scnaf scanf 16 #define scanfi(x) scanf("%d",&x) 17 #define scanfd(x) scanf("%lf",&x) 18 #define scanfl(x) scanf("%lld",&x) 19 #define scanfc(x) scanf("%c",&x) 20 #define scanfs(x) scanf("%s",x) 21 #define maxn 510 22 #define maxm 10010 23 #define inf 1061109567 24 #define Eps 0.00001 25 const double PI=acos(-1.0); 26 #define mod 1000000007 27 #define MAXNUM 10000 28 void Swap(int &a,int &b) {int t=a;a=b;b=t;} 29 int Abs(int x) {return (x<0)?-x:x;} 30 typedef long long ll; 31 typedef unsigned int uint; 32 33 int dp[maxm]; 34 35 int main() 36 { 37 //freopen("data.in","r",stdin); 38 //freopen("data.out","w",stdout); 39 //clock_t st=clock(); 40 int T;scanf("%d",&T); 41 while(T--) 42 { 43 int E,F,p,w,n;scanf("%d%d",&E,&F);F-=E; 44 memset(dp,0x3f,sizeof(dp));scanf("%d",&n); 45 dp[0]=0; 46 for(int i=1;i<=n;i++) 47 { 48 scnaf("%d%d",&p,&w); 49 for(int j=w;j<=F;j++) 50 dp[j]=min(dp[j],dp[j-w]+p); 51 } 52 if(dp[F]==inf) printf("This is impossible.\n"); 53 else printf("The minimum amount of money in the piggy-bank is %d.\n",dp[F]); 54 } 55 //clock_t ed=clock(); 56 //printf("\n\nTime Used : %.5lf Ms.\n",(double)(ed-st)/CLOCKS_PER_SEC); 57 return 0; 58 }

 

转载于:https://www.cnblogs.com/CtrlKismet/p/6719579.html

总结

以上是生活随笔为你收集整理的HDOJ1114解题报告【完全背包】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。