学习了二进制优化,吼吼!写个模板,虽然这种类型并不需要模板,但是写一个,备忘……
模板:
int dp[N];
void OneZeroPack( int v , int n , int w ){
for( int i = v ; i >= n ; i-- )
dp[i] = max( dp[i] , dp[i-n] +w ) ;
}
void CompletePack( int v , int n , int w ){
for( int i = n ; i <= v ; i++ )
dp[i] = max( dp[i] , dp[i-n] +w ) ;
}
void MultipliePack( int v , int c, int w , int n){
if( n*c >= v ){
CompletePack( v , c , w ) ;
return ;
}
int k = 1 ;
while( k < n ){
OneZeroPack( v , k*c , k*w ) ;
n -= k ;
k <<= 1 ;
}
OneZeroPack( v , n*c , n*w ) ;
}
我的代码:
HDU1059 Dividing
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 60006
#define max(a,b) a > b ? a : b
int V,num[7],dp[N];
void OneZeroPack(int c){ //01背包
for( int i = V ; i >= c ; i-- ){
dp[i] = max( dp[i] , dp[i-c] + c );
}
}
void CompletePack(int c){ //完全背包
for( int i = c ; i <= V ; i++ )
dp[i] = max( dp[i] , dp[i-c] + c) ;
}
void MultiplePack(){ //多重背包
for( int i = 1 ; i <= 6 ; i++ ){
if( i * num[i] >= V )
CompletePack(i) ;
else{
int k=1;
while( k < num[i] ){ //二进制优化
OneZeroPack( i*k ) ;
num[i] -= k;
k <<= 1;
}
OneZeroPack( num[i]*i ) ;
}
}
}
int main() {
int count=0;
while(1) {
count++ ;
int sum=0;
memset( num , 0 ,sizeof(num) );
memset( dp , 0 ,sizeof(dp) );
for( int i = 1 ; i <= 6 ; i++ ){
scanf( "%d" , &num[i] );
sum += ( num[i] * i) ;
}
if( !sum )
break ;
printf( "Collection #%d:\n" ,count ) ;
if( sum&1 )
printf( "Can't be divided.\n\n" ) ;
else
{
V = sum/2;
MultiplePack();
if( dp[V] == V )
printf( "Can be divided.\n\n" ) ;
else
printf( "Can't be divided.\n\n" ) ;
}
}
return 0;
}
HDU 2191悼念512汶川大地震遇难同胞——珍惜现在,感恩生活
#include <cmath>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
//#define LOCAL
#define N 105
using namespace std;
int dp[N];
void OneZeroPack( int v , int n , int w ){
for( int i = v ; i >= n ; i-- )
dp[i] = max( dp[i] , dp[i-n] +w ) ;
}
void CompletePack( int v , int n , int w ){
for( int i = n ; i <= v ; i++ )
dp[i] = max( dp[i] , dp[i-n] +w ) ;
}
void MultipliePack( int v , int c, int w , int n){
if( n*c >= v ){
CompletePack( v , c , w ) ;
return ;
}
int k = 1 ;
while( k < n ){
OneZeroPack( v , k*c , k*w ) ;
n -= k ;
k <<= 1 ;
}
OneZeroPack( v , n*c , n*w ) ;
}
int main() {
#ifdef LOCAL
freopen("Input.txt","r",stdin);
freopen("Output.txt","w",stdout);
#endif
int C , n , m , p , h , c , i ;
scanf( "%d" , &C ) ;
while( C-- ){
memset( dp , 0 , sizeof( dp ) ) ;
scanf( "%d%d" , &n , &m ) ;
for( i = 1 ; i <= m ; i++ ){
scanf( "%d%d%d" , &p , &h , &c ) ; //价 重 袋数
MultipliePack( n , p , h , c ) ;
}
printf( "%d\n" , dp[n] );
}
return 0;
}
感谢 xiaod牛!
分享到:
相关推荐
背包之01背包、完全背包、多重背包详解.
多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包...
用贪心算法解决多重背包问题的C++解决方法
多重背包队列优化,高效代码,完美解决,noip的算法问题
多重背包单调队列优化问题.pdf
使用贪心算法解决多重背包问题(物体可拆分)的具体C++代码
(多重)背包(含详细讲解)
北大POJ1014-Dividing【DFS】【多重背包+二进制优化】 解题报告+AC代码
晒代码之二——多重背包(POJ1276)
二维多重背包问题及基于遗传算法的解决方案.rar
背包问题九讲(包含01背包,多重背包,完全背包等)
名称:Knapsack 类型:可视化多重背包问题计算器 开发工具:vs2008 技术平台:C# 作者:FIA E-mail:iamfia@sina.com 完全开源 仅供参考
背包问题详解 01背包,完全背包,多重背包,混合背包,二维费用背包,分级背包,泛化物品等等的分析思路,解题技巧,还有各种背包问题的题目解答。
int MultiPack_3(int n, int c) { //cur[j]表示给定i个物品的情况下,背包容量为j时,对物品进行第k次选择时所能获得的最优
本代码来自于我的文章,如有特殊需求可私信本人。程序错误可在我的文章下面提出问题,详细讲解请看我的文章,请各位大佬支持支持
背包问题(0-1背包,完全背包,多重背包知识概念详解)内含实例代码解析,详细讲解了背包的基本概念及简单运用问题
多重背包问题 III.md
多重背包问题 I.md
多重背包问题 II.md