首页 > 代码库 > HDU 3732 Ahui Writes Word(多重背包)
HDU 3732 Ahui Writes Word(多重背包)
HDU 3732 Ahui Writes Word(多重背包)
http://acm.hdu.edu.cn/showproblem.php?pid=3732
题意:
初始有N个物品, 每个物品有cost[i]花费和val[i]价值, 你有m元钱, 现在问你最多能买多少总价值的物品?
其中N<=10W, m<=1W. 且cost[i]和val[i]都在[0,10]范围.
分析:
本题初看直接用01背包来做是直观的想法. 但是考虑到01背包的复杂度为O(N*m), 这么大的复杂度肯定不行.
然后我们发现其实每种物品只与它的cost[i]和val[i]有关, 如果某两个物品的cost[i]和val[i]完全相等, 我们可以把这两种物品合并(看出一种物品但是数量叠加), 最终我们直接解决一个多重背包问题即可. 如果是多重背包问题,复杂度为O(m*sum( log(num[i]) ) ) 其中 num[i]的和为N.
初始我们读取输入, 然后我们把所有的物品排序,然后在分类之后就构成了n种物品, 每种物品具有num[i]个的多重背包问题.
令dp[i][j]==x 表示购买前i种物品时总花费<=j时, 可以获得的最大价值为x.
初始化: dp全为0.
对于第i种商品, 有下面两种情况:
如果val[i]*num[i]>=m, 就做一次完全背包.
如果val[i]*num[i]<m, 就把第i种物品重新分类, 并做k+1次01背包.
最终所求: dp[n][m]的值.
程序实现, 用的滚动数组逆向递推, 所以dp只有[j]一维.
AC代码:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=121+5; int n;//合并之后n种物品 int m;//最大花费值 int val[maxn]; //新分类i物品价值 int num[maxn]; //新分类i物品数目 int cost[maxn];//新分类i物品花费 int dp[10000+5]; //1次01背包过程 void ZERO_ONE_PACK(int cost,int val) { for(int i=m;i>=cost;i--) dp[i] = max(dp[i], dp[i-cost]+val); } //1次完全背包过程 void COMPLETE_PACK(int cost,int val) { for(int i=cost;i<=m;i++) dp[i] = max(dp[i], dp[i-cost]+val); } //1次多重背包过程 void MULTIPLY_PACK(int cost,int val,int sum) { if(cost*sum>=m) { COMPLETE_PACK(cost,val); return ; } int k=1; while(k<sum) { ZERO_ONE_PACK(cost*k,val*k); sum-=k; k*=2; } ZERO_ONE_PACK(cost*sum, val*sum); } //Node用于保存原始输入的每个单词属性 struct Node { int v,c; bool operator<(const Node &rhs)const { return v<rhs.v || (v==rhs.v && c<rhs.c); } bool operator==(const Node &rhs)const { return v==rhs.v && c==rhs.c; } }nodes[100000+5]; int N;//原始N个单词 int main() { while(scanf("%d%d",&N,&m)==2) { //读取输入 for(int i=1;i<=N;i++) { char str[20]; scanf("%s %d%d",str,&nodes[i].v,&nodes[i].c); } //将原始输入物品合并再分类 sort(nodes+1,nodes+N+1); n=1; val[n]=nodes[1].v; cost[n]=nodes[1].c; num[n]=1; for(int i=2;i<=N;i++) { if(nodes[i]==nodes[i-1]) num[n]++; else { n++; val[n]=nodes[i].v; cost[n]=nodes[i].c; num[n]=1; } } //递推输出 memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) MULTIPLY_PACK(cost[i],val[i],num[i]); printf("%d\n",dp[m]); } return 0; }
HDU 3732 Ahui Writes Word(多重背包)