首页 > 代码库 > HDU 1085 多重背包转化为0-1背包问题
HDU 1085 多重背包转化为0-1背包问题
题目大意:
给定一堆1,2,5价值的硬币，给定三个数表示3种价值硬币的数量，任意取，找到一个最小的数无法取到
总价值为M = v[i]*w[i](0<=i<3)
那么在最坏情况下M个数都能取到 ， M+1必然取不到
所以给M+1个背包，往里面塞东西，最后由前往后检测，找到第一个无法取满的背包的体积
这道题目里，每一种物品的v*w必然小于M+1，所以不出现完全背包的情况，全部采用多重背包转化为0-1背包解决问题即可
1 #include <cstdio> 2 #include <cstring> 3 4 using namespace std; 5 #define max(a,b) a>b?a:b 6 const int N = 10000; 7 8 int dp[N] , a[3] , M; 9 int v[3] = {1 , 2 , 5};10 void zeroPack(int w , int v)11 {12 for(int i = M ; i >= w ; i--)13 dp[i] = max(dp[i-w]+v , dp[i]);14 }15 16 void multiPack(int n , int w , int v)17 {18 int t = 1;19 while(n > t){20 zeroPack(t*w , t*v);21 n -= t;22 t <<= 1;23 }24 if(n > 0) zeroPack(n*w , n*v);25 }26 27 int main()28 {29 while(1){30 M = 0;31 for(int i = 0 ; i<3 ; i++){32 scanf("%d" , a+i);33 M += a[i] * v[i];34 }35 if(M == 0) break;36 //这里加一表示可能你加起来的总值都能够取到，但是多加个一，那么必然会有一个最大值取不到37 M += 1; 38 memset(dp , 0 ,sizeof(dp));39 for(int i = 0 ; i<3 ; i++){40 multiPack(a[i] , v[i] , v[i]);41 }42 43 int k = 0;44 while(dp[k] == k) k++;45 printf("%d\n" , k);46 }47 return 0;48 }
HDU 1085 多重背包转化为0-1背包问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。