HDU 2844 混合背包、

程序员桂香技术 2022年11月10日

0 收藏 694 点赞 4,748 浏览 1106 个字

题意：一个人想买手表，给你n个价值的硬币，然后给你n个价值硬币对应的个数、但是呢，这个人只知道这个手表的价格不超过m元、问他最多能买多少种价值的手表

思路：dp背包专题但是- – 一直不知道该怎么dp 终于想通了、

PS：对于背包dp说一说自己的理解吧（虽然不知道有什么用）　一旦涉及到dp 你就要考虑dp数组里面存的是什么，另外一维数组的话你就要考虑dp[i]中，那个i代表的是什么，同理二维数组也是一样、然后写出状态转移方程，你的状态转移方程一定要和你dp数组里面存的状态是相一致的、

 #include<cstdio>
 #include<cstring>
 #include<cmath>
 #include<algorithm>
 using namespace std;
 const int qq=;
 int a[qq],c[qq];
 int dp[];        //dp[i]代表价值为i能用硬币的最大数量、
 int m;
 void wanquan(int x,int y)
 {
     for(int i=x*y;i<=m;++i)
         if(dp[i-x])
             dp[i]=max(dp[i],dp[i-x]+y);
         else if(i-x==)
             dp[i]=max(dp[i],dp[i-x]+y);
     return;
 }
 void beibao(int x,int y)
 {
     int c=x*y;
     for(int i=m;i>=c;--i)
         if(dp[i-c])
             dp[i]=max(dp[i],dp[i-c]+y);
         else if(i-c==)
             dp[i]=max(dp[i],dp[i-x]+y);
 }
 void f(int x,int y)
 {
     if(x*y>=m){
         wanquan(x,);
         return;
     }
     int t=;
     while(y>=t){
         beibao(x,t);
         y=y-t;
         t=t<<;
     }
     if(y)    beibao(x,y);
 }
 int main()
 {
     int n;
     while(~scanf("%d%d",&n,&m)&&(n||m)){
         memset(dp,,sizeof(dp));
         for(int i=;i<n;++i)
             scanf("%d",&a[i]);
         for(int i=;i<n;++i)
             scanf("%d",&c[i]);
         int count=;
         for(int i=;i<n;++i)
             f(a[i],c[i]);
         int sum=;
     //    for(int i=1;i<=m;++i)
     //        printf("%d ",dp[i]);
         for(int i=;i<=m;++i)        //dp[i]不为0也就是说能用所拥有的硬币组成价值i
             if(dp[i])    ++sum;
         printf("%d\n",sum);
     }
     return ;
 }