首页 > 代码库 > HDU 2191 悼念汶川地震（AC代码）多重背包
HDU 2191 悼念汶川地震（AC代码）多重背包
0MS 1084K 706B C++
这是用“转01背包”实现的，速度还这么快，还需优化不？
1 # include <stdio.h> 2 # include <string.h> 3 int dp[101] ;//转成01背包的解法，没有任何优化。 4 int max(int a,int b) 5 { 6 return a>b?a:b; 7 } 8 int main () 9 {10 int T, ans, n, m ;11 int p, h, c, i, j ;12 scanf ("%d", &T) ;13 while (T--)14 {15 scanf ("%d%d", &n, &m) ; //n是经费，m是种类16 memset (dp, 0, sizeof(dp)) ;17 ans = 0 ;18 while (m--)19 {20 scanf ("%d%d%d", &p, &h, &c) ;21 for(i = 1 ; i<=c ; i++) //m是经费22 {23 for(j = n ; j >= p ;j--)24 {25 dp[j]=max(dp[j],dp[j-p]+h);26 }27 }28 }29 printf ("%d\n", dp[n]) ;30 }31 return 0 ;32 }
思路：多重背包转成01背包，怎么转？把一种大米看成一堆单个的物品，每件物品要么装入，要么不装。复杂度比01背包要大，假设每种大米有10件，那么在01背包的复杂度O(vn)的基础上，每种大米的计算量要乘以10，那么复杂度O（10*vn）。这是假设每种大米数量为10的情况，若为m，那么复杂度O（vnm），很大。这个做法太粗糙了，但就是AC了。
其他没实现的想法：按照完全背包的做法，在里面加一些东西来控制“数量不够”的情况。当数量已达上限，用做大数量来代替，那么需要比较的两个dp值就是dp[j]与dp[j-1]，分别代表不装、装满。另用一个数组来记录每个不同的经费上限对应dp数组中所用的第i种大米的数量。这个数组要在不同i时更新为0，有开销。这个想法实现不了。
另外可行的思路：
①在转成01背包上作优化。完全背包+01背包来解，即：某一种大米的数量*单价>=经费，那么就是完全背包型；否则就是01背包型。但如果遇到都是01背包型，此优化没用了。
②01背包+二进制法。 还没理解二进制的真谛，看到别人好像实现了。
③队列法。复杂度为O（vn），还没理解。
附件一：未实现的想法
1 #include <iostream> 2 #define limit 110 3 using namespace std; 4 int p[limit]; //单价 5 int h[limit]; //净重 6 int c[limit]; //数量上限 7 int u[limit]; //已买的数量 8 int dp[limit]; 9 int max(int a,int b)10 {11 return a>b?a:b;12 }13 void cal(int n,int m)14 {15 int temp=0,j,i;16 for(i=0;i<m;i++)17 {18 for(j=0;j<=n;j++) //初始化数组u19 u[j]=0;20 for( j=p[i];j<=n;j++)21 {22 temp=max( dp[j],dp[j-p[i]]+h[i] );23 if(temp==dp[j-p[i]]+h[i]) //需要加多一件24 {25 if(u[j-p[i]]<c[i]) //第i件还有剩余，可以买。26 {27 u[j]=u[j-p[i]]+1;28 dp[j]=temp;29 }30 else //被用光了，但是为了防止前大于后的情况，在不能追加的情况下，仍需比较前后的大小，保证后总大于前31 {32 dp[j]=max(dp[j-1],dp[j]); //仅需比较1个，因前面每个所使用的并不是升序的，可能无序的33 if(dp[j]==dp[j-1])34 u[j]=u[j-1];//因为u[j]本来就是0，所以else的情况不用赋零35 }36 }37 }38 }39 return;40 }41 void main()42 {43 int q,n,m,i;44 scanf("%d",&q);45 while(q--)46 {47 memset(dp,0,sizeof(dp));48 scanf("%d%d",&n,&m); //经费的金额 大米的种类49 for(i=0;i<m;i++)50 {51 scanf("%d%d%d",&p[i],&h[i],&c[i]); //分别表示每袋的价格、每袋的重量以及对应种类大米的袋数52 }53 cal(n,m);54 printf("%d\n",dp[n]);55 }56 }
附件二：可行的思路①
1 #include<iostream> 2 const int N=110; 3 using namespace std; 4 int n,m; 5 6 struct Rice{ 7 int price; 8 int weight; 9 int number;10 }rice[N];11 int dp[N];12 int max(int a,int b)13 {14 return a>b?a:b;15 }16 //完全背包17 void CompletePack(int cost,int weight){18 for(int i=cost;i<=n;i++){19 dp[i]=max(dp[i],dp[i-cost]+weight);20 }21 }22 //01背包23 void ZeroOnePack(int cost,int weight){24 for(int i=n;i-cost>=0;i--){25 dp[i]=max(dp[i],dp[i-cost]+weight);26 }27 }28 29 //多重背包30 void MultiplePack(int cost,int weight,int number){31 //如果大于等于金额，就按完全背包处理（此时相当于不限定袋数）32 if(cost*number>=n){33 CompletePack(cost,weight);34 return ;35 }36 int k=1;37 while(k<number){38 ZeroOnePack(k*cost,k*weight);39 number-=k;40 k*=2;41 }42 ZeroOnePack(number*cost,number*weight);43 }44 45 int main(){46 int _case;47 scanf("%d",&_case);48 while(_case--){49 scanf("%d%d",&n,&m);50 memset(dp,0,sizeof(dp));51 for(int i=0;i<m;i++){52 scanf("%d%d%d",&rice[i].price,&rice[i].weight,&rice[i].number);53 }54 for(i=0;i<m;i++){55 MultiplePack(rice[i].price,rice[i].weight,rice[i].number);56 }57 printf("%d\n",dp[n]);58 }59 return 0;60 }
HDU 2191 悼念汶川地震（AC代码）多重背包
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。