作为一个oier，以及大学acm党背包是必不可少的一部分。好久没做背包类动规了。久违地练习下-。-
dd__engi的背包九讲：http://love-oriented.com/pack/
鸣谢http://blog.csdn.net/eagle_or_snail/article/details/50987044，这里有大部分比较有趣的dp练手题。
hud 2602 01背包板子题
#include<cstdio>
#include<iostream>
#include<cstring>
#define clr(x) memset(x,0,sizeof(x))
using namespace std;
struct node
{
int cost,val;
}bag[];
int dp[];
int main()
{
int T,n,m;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
clr(dp);
clr(bag);
for(int i=;i<=n;i++)
scanf("%d",&bag[i].val);
for(int i=;i<=n;i++)
scanf("%d",&bag[i].cost);
for(int i=;i<=n;i++)
for(int j=m;j>=bag[i].cost;j--)
{
if(dp[j]<dp[j-bag[i].cost]+bag[i].val)
dp[j]=dp[j-bag[i].cost]+bag[i].val;
}
printf("%d\n",dp[m]);
}
return ;
}
01背包
hdu 2844 Coins 多重背包
就是一个10w的多重背包，每个物品的cost同时也作为value去做背包，我们求的是每个容量下的价值，所以没法做背包九讲里提到的对最终目标的常数优化。那么我们做完以后，统计一下背包里dp[i]==i的空间i总数即为答案。
#include<cstdio>
#include<iostream>
#include<cstring>
#define clr(x) memset(x,0,sizeof(x))
#define MAXN 100010
using namespace std;
int dp[MAXN];
struct node
{
int num,cost;
}good[MAXN];
int n,m,s,t,l,k,ans;
int max(int a,int b)
{
return a>b?a:b;
}
void zeroonepack(int cost,int val)
{
for(int i=m;i>=cost;i--)
{
dp[i]=max(dp[i],dp[i-cost]+val);
}
return ;
}
void completepack(int cost,int val)
{
for(int i=cost;i<=m;i++)
{
dp[i]=max(dp[i],dp[i-cost]+val);
}
return ;
}
void multipack(int cost,int val,int num)
{
if(cost*num>=m)
{
completepack(cost,val);
}
else
{
int t=;
while(t<=num)
{
zeroonepack(t*cost,t*val);
num-=t;
t*=;
}
zeroonepack(num*cost,num*val);
}
return ;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF && m!= && n!=)
{
clr(dp);
for(int i=;i<=n;i++)
{
scanf("%d",&good[i].cost);
}
for(int i=;i<=n;i++)
{
scanf("%d",&good[i].num);
}
for(int i=;i<=n;i++)
{
multipack(good[i].cost,good[i].cost,good[i].num);
}
ans=;
for(int i=;i<=m;i++)
{
if(dp[i]==i)
ans++;
}
printf("%d\n",ans);
}
return ;
}
多重背包
hdu 2159 FATE 完全背包
一个二维完全背包，将消耗忍耐度和杀怪数作为二维的cost，然后将求解每个忍耐度和杀怪数下经验值的最大值作为最大价值。我们做一遍二维完全背包，然后找杀怪数满（即dp[s][i]）时最小的经验值超过升级所需经验值n的i，这个i即为最小忍耐度，然后m-i即为答案。
#include<cstdio>
#include<iostream>
#include<cstring>
#define clr(x) memset(x,0,sizeof(x))
#define MAXN 110
using namespace std;
int dp[MAXN][MAXN],v[MAXN],c[MAXN];
int n,m,k,s,t,l,ans,minn;
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF)
{
clr(dp);
for(int i=;i<=k;i++)
{
scanf("%d%d",&v[i],&c[i]);
}
for(int i=;i<=k;i++)
{
for(int j=;j<=s;j++)
{
for(int t=c[i];t<=m;t++)
dp[j][t]=max(dp[j][t],max(dp[j-][t],dp[j-][t-c[i]]+v[i]));
}
}
if(dp[s][m]<n)
{
printf("-1\n");
}
else
{
minn=m;
for(int i=;i<=m;i++)
if(dp[s][i]>=n && i<minn)
{
minn=i;
break;
}
printf("%d\n",m-minn);
}
}
return ;
}
二维完全背包
poj 1170 Shopping Offers 状压+完全背包
最多五个物品，每个物品最多五件。因此可以将每个状态，cost，最终状态压缩成五位的六进制数，然后做求最小值的完全背包就行了。当然这题还是用编号的形式给出物品的，你需要把物品弄成连续的编号再做压缩操作。
#include<cstdio>
#include<iostream>
#include<cstring>
#define clr(x) memset(x,0,sizeof(x))
#define clrmax(x) memset(x,0x3f3f3f3f,sizeof(x))
#define MAXN 1000010
using namespace std;
int dp[MAXN];
int v[MAXN],c[MAXN];
int inf[MAXN];
int bit(int n)
{
int l=;
n--;
while(n--)
l*=;
return l;
}
bool infer(int i,int j)
{
while(j)
{
if(i%<j%)
return false;
i/=;
j/=;
}
return true;
}
int main()
{
int n,m,maxn,ans,t,k,l,r,cnt,flag,num;
while(scanf("%d",&n)!=EOF)
{
m=;
clr(inf);
clrmax(dp);
for(int i=;i<=n;i++)
{
scanf("%d",&k);
inf[k]=i;
c[i]=bit(i);
scanf("%d%d",&num,&v[i]);
m+=bit(i)*num;
}
cnt=n;
scanf("%d",&k);
for(int i=;i<=k;i++)
{
scanf("%d",&l);
flag=;
r=;
for(int i=;i<=l;i++)
{
scanf("%d%d",&n,&t);
if(inf[n]== || flag==)
{
flag=;
continue;
}
r+=bit(inf[n])*t;
}
if(flag==)
{
c[++cnt]=r;
scanf("%d",&v[cnt]);
}
else
{
scanf("%d",&r);
}
}
dp[]=;
for(int i=;i<=cnt;i++)
{
for(int j=c[i];j<=m;j++)
if(infer(j,c[i]))
{
dp[j]=min(dp[j],dp[j-c[i]]+v[i]);
}
}
printf("%d\n",dp[m]);
}
return ;
}
状压完全背包
hdu 3092 Least common multiple 转化为01背包
把一个数n进行划分，求最大的lcm，并将n%mod。
我们先不要在意%mod。对于一个数n，我们发觉（只有质数或者相同质数的积和剩下一堆1）的划分的情况下n的lcm会达到最大——因为，在第p次非质数的划分你可以拆解成n个质数相乘，将n个质数或者相同质数的乘积唯一化为k个作为划分后，这k个数的和小于等于该非质数，显然后者能使第p次划分完之后剩下的划分数字更大，得出来的lcm更大。当然剩下的多余的数全部拆解成1，这样对答案是不影响的（没有贡献的）。你可以发觉这很像一个01背包，而且是最大容量为n的背包，而物品则是质数或相同质数的积，cost为该数，value也为该数，那么对于每个状态的转移为：dp[j]=max(dp[j-c[i]]*v[i],dp[j])。并且每个物品只影响一次，即为01背包，毕竟一个质数对该状态的贡献只有乘一次该质数而不能多次。所以加上一些n个相同质数的积的细节处理（想想为什么）后做个01背包，即能求解出答案 dp[n]。
然而相乘数字太大，并且需要mod，我们可以用一个数组dp来存进行特殊处理过的大小以方便进行动态规划，另一个数组ans来存答案，包括%mod。将dp中的数全部log10以表示更大范围，每次转移就变为dp[j]=max(dp[j-c[i]]+log10（v[i]）,dp[j])便于比较大小，dp[j]被更新后ans也同样更新，并且%mod。
最后求出来ans[n]即为答案。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define clr(x) memset(x,0,sizeof(x))
#define MAXN 10010
using namespace std;
double dp[MAXN];
int ans[MAXN];
int prime[MAXN],inf[MAXN];
int n,m,s,k,t,mod,cnt;
double u,v,b,x;
void primer(int n)
{
clr(inf);
cnt=;
for(int i=;i<=n;i++)
{
if(!inf[i])
{
prime[++cnt]=i;
inf[i]=;
}
for(int j=;j<=cnt;j++)
{
if(prime[j]*i>n) break;
inf[prime[j]*i]=;
if(i%prime[j]==)
break;
}
}
return ;
}
int main()
{
primer();
while(scanf("%d%d",&n,&mod)==)
{
clr(dp);
for(int i=;i<=n;i++)
ans[i]=;
for(int i=;i<=cnt && prime[i]<=n;i++)
{
u=log10(prime[i]*1.0);
for(int j=n;j>=prime[i];j--)
{
for(int k=,t=prime[i];t<=j;k++,t=t*prime[i])
if(dp[j-t]+k*u>dp[j])
{
dp[j]=dp[j-t]+k*u;
ans[j]=(ans[j-t]*t)%mod;
}
}
}
printf("%d\n",ans[n]);
}
return ;
}
背包
poj 1015 Jury Compromise 区间右移+输出路径
这一题，我们需要得出最小的$ |D[sum]-P[sum]|$的情况下最大的$ |D[sum]+P[sum]|$。
那我们可以考虑做一个二维的01背包，其中背包的两个费用为人数和当前做到第i个人的d[sum]-p[sum]。因为这样会涉及负数，因此将整个区间右移。考虑到$ m\le 20$ 以及 $ -20 \le d[i]-d[j] \le 20 $ 因此区间为[-400,400]，将其右移为[0.800]。然后我们要求的是背包在当前费用下最大的d[sum]+p[sum]。在按照d[sum]-p[sum]这个费用循环时注意，背包上限是(400<400+c[i])?400:400+c[i]下限是c[i]-400>-400?c[i]-400:-400。
背包处理完以后，在400附近找最靠近400的i，即最小的|d[sum]-p[sum]|，并且 dp[n][m][400+i]是最大的，然后输出(i+dp[n][m][400+i])/2为P[sum]，(i-dp[n][m][400+i])/2为D[sum]。
接下来就是按路径输出的问题了，这个路径背包九讲里有讲过怎么获得我就不再赘言了。但是poj说好的是special judge，然后发觉应该输出最大字典序才行。。坑死了，害我看了好久。
#include<cstdio>
#include<iostream>
#include<cstring>
#define clr(x) memset(x,0,sizeof(x))
#define clrmin(x) memset(x,-0x3f3f3f3f,sizeof(x))
using namespace std;
int dp[][][];
int c[],v[],ans[];
int n,m,k,s,t,l,r;
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int kase=,fit;
while(scanf("%d%d",&n,&m)!=EOF && n> && m>)
{
clrmin(dp);
dp[][][]=;
for(int i=;i<=n;i++)
{
scanf("%d%d",&l,&r);
c[i]=l-r;
v[i]=l+r;
dp[i][][]=;
}
for(int i=;i<=n;i++)
{
for(int j=m;j>;j--)
{
for(int k=(<+c[i])?:+c[i];k>=c[i]- && k>=-;k--)
{
dp[i][j][k+]=max(dp[i-][j][k+],dp[i-][j-][k-c[i]+]+v[i]);
}
}
/* for(int ii=0;ii<=2;ii++)
{
for(int jj=398;jj<=406;jj++)
printf("%d ",dp[i][ii][jj]>=0?dp[i][ii][jj]:-1);
printf("\n");
} */
// printf("%d\n",dp[i][0][400]);
}
for(int i=;i<=;i++)
{
if(dp[n][m][+i]> || dp[n][m][-i]>)
{
if(dp[n][m][+i]>dp[n][m][-i])
l=i;
else
l=-i;
break;
}
}
printf("Jury #%d\n",++kase);
printf("Best jury has value %d for prosecution and value %d for defence:\n",(l+dp[n][m][+l])/,(dp[n][m][+l]-l)/);
l=+l;
t=m;
for(int i=n;i>=;i--)
if(dp[i][m][l]==dp[i-][m-][l-c[i]]+v[i])
{
ans[m]=i;
m--;
l-=c[i];
if(m==)
break;
}
for(int i=;i<=t;i++)
printf(" %d",ans[i]);
printf("\n\n");
}
return ;
}
二维01背包
做了这么些题，可以发觉背包题需要对费用很敏感，对于是精确到某个容量下的（即装满）的背包和非精确（即最多为该容量）的背包，赋初值的方式是不同的。还有要善于发掘背包的费用，费用可以是任何可以用来递推的下标。可能是多维（2以上）要擅用状态压缩使得问题简单化。
当然对于dp都有一个共同点：数据范围特别小。注意下数据范围有可能就能发现他是一道dp甚至背包，从而快速解决。