问题描述：
有若干价值为分别为1，2 ，3，4，5，6的大理石，求总价值的均分策略。设价值为V的石头重量为V,这批石头的总价值为SUM,则问题转化为选取若干大理石将容量为SUM/2的背包装满。
背包问题（参考“背包问题9讲”）
有N件物品和一个容量为V的背包，第i件物品的费用是c[i]，价值是w[i]。 f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值,则有：
状态转移方程
f[i][v] = max{f[i-1][v], f[i-1][v-c[i]]+w[i]}&&&&&&
解法 O(VN)
for i = 1…N&
&&& for v = V…c[i]&
&&&&&&& f[v] = max{f[v], f[v-c[i]]+w[i]};
procedure ZeroOnePack(cost, weight)&
&& for v = V…cost&
&&&&&&&& f[v] = max{f[v], f[v-cost]+weight}
要求恰好装满背包： f[0] = 0, f[1…V] = –1&
只要求价值最大:&& f[0…V] = 0&
状态转移方程& O(V*Σ(V/c[i]))
f[i][v] = max{f[i-1][v-k*c[i]]+k*w[i]|0&=k*c[i]&=v}
转化为0-1背包问题 O(VN)
for i = 1…N&
&&& for v = cost…V&
&&&&&&&& f[v] = max{f[v], f[v-cost]+weight}
procedure CompletePack(cost, weight)&
&&&& for v = cost…V&
&&&&&&&&& f[v] = max{f[v], f[v-cost]+weight}
多重背包 (指定每件物品的个数n[i])
状态转移方程 O(V*Σn[i])
f[i][v] = max{f[i-1][v-k*c[i]]+k*w[i]|0&=k&=n[i]}
二进制优化 O(V*Σlog(n[i]))
将第i种物品以2的指数分堆：1，2，4，…，2^(k-1)，n[i]-2^k+1,且&
k是满足n[i]-2^k+1&0的最大整数。每次处理一堆而不是一个物品。
procedure MultiplePack(cost, weight, amount)&
&&& if cost*amount&=V&
&&&&&&&&&& CompletePack(cost, weight)&
&&&&&&&&&& return&
&&& integer k=1&
&&& while k&amount&
&&&&&&&&&&& ZeroOnePack(k*cost, k*weight)&
&&&&&&&&&&& amount = amount – k&
&&&&&&&&&&& k = k * 2&
&&& ZeroOnePack(amount*cost, amount*weight)
当输入样本特别大时，比如给出上百万件物品，这时候仅靠优化算法仍然不能使运行时间降到满意的范围。可考虑如何减少输入样本。poj1014的discussion上有一个非常巧妙的“取模优化”法。
设价值为v(1&=v&=6)的物品共有n件，我们希望找到一个比较小的数s(s&n), 且将n件物品v减少到s或s-1件，问题的可分性不变。考虑不可分和可分两种情况：
下面依次考虑v=1,2,3,4,5,6时如何根据“抽屉原理”得到满足条件I和II的s。
v=1时，s=6&& 替换法： if(n&6) n=6-n%2
1总能被其它价值替换，所以满足条件I不是问题，为满足条件2，s必须大于6。 因为6是其它价值物品中一次可替换最多1的物品。
v=2时，s=5&& 替换法： if(n&5) n=4+n%2
由1*(2-1)+3*(2-1)+4*(1-1)+5*(2-1)+6*(1-1) = 9 & 2*5知，s=4时满足条件I。但这里要注意，如果另一堆可替换2的是两个5，那么一次就可替换5个2。为满足条件 II,s不能小于5。所以这里s是5而不是4。
v=3时，s=8&&& 替换法： if(n&8) n=8-n%2
由1*(3-1)+2*(3-1)+4*(3-1)+5*(3-1)+6*(1-1) = 24 & 3*9知，s=8时满足条件I，且最多可替换5个3，所以s=8&5也满足条件II。
v=4时，s=8&&& 替换法： if(n&8) n=8-n%2
由1*(4-1)+2*(2-1)+3*(4-1)+5*(4-1)+6*(2-1) = 35 & 4*9知， s=8时满足条件I，且最多可替换5个4，所以s=8&5也满足条件II。
v=5时，s=12&& 替换法： if(n&12) n=12-n%2
由1*(5-1)+2*(5-1)+3*(5-1)+4*(5-1)+6*(5-1) = 64 & 5*13知，s=12满足条件I，且最多可替换6个5，所以s=12&6也满足条件II。
v=6时，s=7&& 替换法：if(n&7) n=6+n%2
由1*(6-1)+2*(3-1)+3*(2-1)+4*(3-1)+5*(6-1) = 45 & 6*8知，s=7满足条件I，且最多可替换5个6，所以s=7&5也满足条件II。
可以看出，“模优化”将无论多么大的输入样本减少到50个以内，极大地减少了计算量，从而显著提高运行效率。而“模优化”的关键就是“抽屉原理”。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：8796次
排名：千里之外
原创：86篇
(2)(1)(69)(1)(5)(11)题意：n件物品，背包大小为C，每件物品有一定的价值和体积，求背包能装的最大价值。
思路：如果用01背包做肯定超时，因为数据给得太大了，我们可以根据价值和体积来区分物品，相当于背包空间和含有的价值 有多个，多重背包，然后用二进制优化，再用01背包来做；
int dp[10005];
int main()
int map[11][11];
while(~scanf("%d%d",&t,&s))
int i,j,k,l;
char c[10001];
memset(map,0,sizeof(map));
memset(dp,0,sizeof(dp));
for(i=1;i&=t;i++)
scanf("%s%d%d",c,&j,&k);
getchar();
map[j][k]+=1;
for(i=1;i&=10;i++)
for(j=1;j&=10;j++)
int tt=1,zz=map[i][j];
while(tt&zz)
for(k=s;k&=tt*j;k--)
dp[k]=max(dp[k],dp[k-tt*j]+tt*i);
for(k=s;k&=zz*j;k--)
dp[k]=max(dp[k],dp[k-zz*j]+zz*i);
printf("%d\n",dp[s]);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1833次
排名：千里之外
原创：93篇
(20)(26)(2)(4)(22)(26)hdu1059 dp(多重背包二进制优化) - 奚政 - 博客园
题意，现在有价值为1、2、3、4、5、6的石头若干块，块数已知，问能否将这些石头分成两堆，且两堆价值相等。
很显然，愚蠢的我一开始并想不到什么多重背包二进制优化```因为我连听都没有听过```不得不吐槽自己的知识面太窄```于是，我用了母函数写这题，母函数的做法并没有问题，但是由于这道题的数据很大，母函数轻轻松松就超时了，于是，我又很努力地在母函数循环的优化上面想出路，改改改，各种改之后依旧TLE，01背包的做法显然也是会超时的，DISCUSS里的母函数做法优化方式都是模上一个大质数，但很明显，只是因为数据较弱才会过的，因为没有人能保证被这个数模掉的那些部分是否可以平分，模掉之后剩下的数也很有可能就因此不能平分了所以这种优化肯定是不可取的。
问过学长粗看了题解之后才知道原来还有一种叫多重背包的东西，学长推荐我看背包九讲，我看了之后才会做这个题目```
多重背包其实本身也是01背包，但由于有多个价值相同的物品，所以有更加优化的解法就是用二进制优化，将相同价值的物品分为 20， 21 ， 22 ，```个，最后再有一部分不能继续向二进制高阶划分的，将这些被划分的物品分别合成一个物品，那么就得到了价值为 1 倍的、2倍的、4倍的```物品，然后再按照01背包的做法，通过二进制数的加和可以实现物品的所有放入情况。
1 #include&stdio.h&
2 #include&string.h&
3 #define max(a,b) a&b?a:b
4 int Va[100],We[100],n[7],dp[200000];
6 int main(){
while(scanf("%d%d%d%d%d%d",&n[1],&n[2],&n[3],&n[4],&n[5],&n[6])!=EOF&&(n[1]!=0||n[2]!=0||n[3]!=0||n[4]!=0||n[5]!=0||n[6]!=0)){
if(c)printf("\n");
printf("Collection #%d:\n",++c);
int i,j,sum=0,
for(i=1;i&=6;i++)sum+=i*n[i];
if(sum%2){
printf("Can't be divided.\n\n");
else mid=sum/2;
memset(dp,-1,sizeof(dp));
int count=0,
for(i=1;i&=6;i++){
while(n[i]&=temp){
Va[++count]=i*
We[count]=
if(n[i]&0){
Va[++count]=i*n[i];
We[count]=n[i];
for(i=1;i&=i++){
for(j=j&=Va[i];j--){
if(dp[j-Va[i]]&=0){
dp[j]=max(dp[j],dp[j-Va[i]]+We[i]);
if(dp[mid]&0)printf("Can be divided.\n\n");
else printf("Can't be divided.\n\n");
阅读(...) 评论()背包问题九讲和源程序(答案)_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
背包问题九讲和源程序(答案)
上传于||暂无简介
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
下载文档到电脑，查找使用更方便
还剩15页未读，继续阅读
你可能喜欢背包问题更深化的理解-多重背包的二进制拆分 - csgc0131123 - 博客园
随笔 - 295, 文章 - 0, 评论 - 5, 引用 - 0
这篇文章主要证明一下多重背包的二进制拆分的可行性与正确性：
类似于二进制的原理：一定可以表达一系列连续的正数，下面用例子证明
& & & &把22进行二进制拆分：
& & & & &成为1,2,4,8,7；由1,2,4,8可以组成1--15之间所有的数，而对于16--22之间的数，可以先减去剩余的7，那就是1--15之间的数可以用1,2,4,8表示了。
NOI 8756:砝码称重V2
总时间限制:&1000ms&内存限制:&65536kB描述
设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重&=100,000），要求：计算用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况。
输入一行，包括六个正整数a1,a2,a3,a4,a5,a6，表示1g砝码有a1个，2g砝码有a2个，&&，20g砝码有a6个。相邻两个整数之间用单个空格隔开。输出以&Total=N&的形式输出，其中N为可以称出的不同重量的个数。样例输入
1 1 0 0 0 0
提示样例给出的砝码可以称出1g，2g，3g三种不同的重量。注意：对于拆分剩余是0，因题目的意思要特别处理。
#include&iostream&
using namespace
#include&cstdio&
int a[]={0,1,2,3,5,10,20};
#define MAX 100100
bool f[MAX];
int val[MAX];
int sum=0;
void input()
int count=0,b=0;
for(int i=1;i&=6;++i)
scanf("%d",&b);
sum+=b*a[i];
count=a[i];
for(int i=1;i&=b;i&&=1)
val[t]=count*i;
val[t]=count*b;
f[0]=true;
for(int i=1;i&=t;++i)
for(int j=j&=val[i];--j)
f[j]=f[j]||f[j-val[i]];/*注意val才是拆成的背包*/
for(int i=1;i&=++i)
printf("Total=%d\n",p);
int main()