本文主要是介绍多重背包转换成0-1背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=2191
多重背包特点:
一种物品有C个（既不是固定的1个，也不是无数个）
优化的方法：
运用神奇的二进制,进行物品拆分,转化成01背包
物品拆分,把13个相同的物品分成4组(1,2,4,6)
用这4组可以组成任意一个1~13之间的数!
原理:一个数总可以用2^k表示
而且总和等于13,所以不会组成超过13的数
所以可将一种有C个的物品拆分成1,2,4,...,2^(k-1),C-(2^k-1)
然后进行01背包
const int Max_N = 1008 ;int N , V ;
int dp[Max_N] , w[Max_N] , v[Max_N] ;void Dvide(int _v , int _w , int S){int x = 1 ;while(S >= x){w[++N] = _w * x ;v[N] = _v * x ;S -= x ;x <<= 1 ;}if(S != 0){w[++N] = _w * S ;v[N] = _v * S ;}
}int main(){int T , M , i , j , _w , _v , _s;cin>>T ;while(T--){cin>>V>>M ;N = 0 ;memset(dp , 0 , sizeof(dp)) ;while(M--){scanf("%d%d%d" , &_v , &_w , &_s) ;Dvide(_v , _w , _s) ;}for(i = 1 ; i <= N ; i++){for(j = V ; j >= v[i] ; j--){dp[j] = max(dp[j] , dp[j-v[i]] + w[i]) ;}}printf("%d\n" , dp[V]) ;}return 0 ;
}
http://acm.hdu.edu.cn/showproblem.php?pid=1059
1 , 2 , 3 ,4 ,5 ,6 有x1 , x2 ,x3 ,x4 ,x5 ,x6个 ，问能否平分成2份和相等。
const int Max_N = 6 * 400 ;int N ;
int v[Max_N] ;void Divide(int _v , int S){int x = 1 ;while(S >= x){v[++N] = x * _v ;S -= x ;x <<= 1 ;}if(S > 0){v[++N] = S * _v ;}
}int x[7] ;
bool dp[210008] ;int main(){int sum , k = 1 , i , j ;while(scanf("%d" ,&x[1])){sum = x[1] ;for(i = 2 ; i <= 6 ; i++){scanf("%d" ,&x[i]) ;sum += i*x[i] ;}if(sum == 0) break ;printf("Collection #%d:\n" , k++) ;if(sum & 1){puts("Can't be divided.") ;puts("") ;continue ;}sum >>= 1 ;N = 0 ;fill(dp , dp+sum+1 , 0) ;dp[0] = 1 ;for(i = 1 ; i <= 6 ; i++)Divide(i , x[i]) ;for(i = 1 ; i <= N ; i++){for(j = sum ; j >= v[i] ; j--){dp[j] |= dp[j-v[i]] ;}}printf("%s\n" , dp[sum]? "Can be divided." : "Can't be divided.") ;puts("") ;}return 0 ;
}
http://acm.hdu.edu.cn/showproblem.php?pid=2844
多重背包问题，用n个物品，每个物品有价值v[i]，每个物品数量限制为c[i]
这道题是问，用所有的硬币能够在m的范围内最多可以组合成多少种价值
对于每个硬币而言:
IF 价值×数量>=V
ELSE
const int Max_N = 100008 ;
const int Max_M = 108 ;int v[Max_N] , c[Max_N] ;
int dp[Max_N] ;
int V , N ;void ZoreOnePack(int v , int w){for(int i = V ; i >= v ; i--)dp[i] = max(dp[i] , dp[i - v] + w) ;
}void CompletePack(int v , int w){for(int i = v ; i <= V ; i++)dp[i] = max(dp[i] , dp[i - v] + w) ;
}int DP(){int x , i , ans = 0 ;fill(dp , dp+1+V , 0) ;for(i = 1 ; i <= N ; i++){if(v[i] * c[i] >= V)CompletePack(v[i] , v[i]) ;else{x = 1 ;while(c[i] >= x){ZoreOnePack(v[i]*x , v[i]*x) ;c[i] -= x ;x <<= 1 ;}if(c[i] > 0)ZoreOnePack(v[i]*c[i] , v[i]*c[i]) ;}}for(i = 1 ; i <= V ; i++)ans += dp[i] == i ;return ans ;
}int main(){int i ;while(cin>>N>>V){if(N == 0 && V == 0) break ;for(i = 1 ; i <= N ; i++)scanf("%d" ,&v[i]) ;for(i = 1 ; i <= N ; i++)scanf("%d" ,&c[i]) ;if(V <= 0)puts("0") ;elsecout<<DP()<<endl ;}return 0 ;
}
这篇关于多重背包转换成0-1背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
