通过之前的博文《白话01背包》对01背包学习进行总结，几个01背包入门题解，给出顺序为难度梯度：
poj3624Charm Bracelet
完全模板题
这里给出 一维和二维的三份代码...为什么有三份....？？对于二维的，有两份，一维的一份.....
二维第一份：
#include<stdio.h>
#include<string.h>
#define MAX1 3410
#define MAX2 12885
int main()
{
int i,j;
int N,M;
int w[MAX1],va[MAX1],dp[MAX1][MAX2];
scanf("%d%d",&N,&M);
for(i=1;i<=N;i++)
scanf("%d%d",&w[i],&va[i]);
//dp过程
memset(dp,0,sizeof(dp));
for(i=1;i<=N;i++)
for(j=1;j<=M;j++)//注意这里j表示背包的容量为j 这里是从1到M递增，第二份代码中将递减
{
if(w[i]<=j)
{
if(dp[i-1][j]<dp[i-1][j-w[i]]+va[i])
dp[i][j]=dp[i-1][j-w[i]]+va[i];
else
dp[i][j]=dp[i-1][j];
}
else
dp[i][j]=dp[i-1][j];
}
printf("%d\n",dp[N][M]);
return 0;
}
二维第二份：只给出dp过程...其他的一样
//dp过程
memset(dp,0,sizeof(dp));
for(i=1;i<=N;i++)
for(j=M;j>=w[i];j--)//注意这里j表示背包的容量为j 这里和第一份不同的就是j只 从M递减到w[i] 作用是一样的
if(dp[i-1][j]<dp[i-1][j-w[i]]+va[i])
dp[i][j]=dp[i-1][j-w[i]]+va[i];
else
dp[i][j]=dp[i-1][j];
下面是一维的状态转移方程
dp[j]=max(dp[j],dp[j-w[i]]+va[i]);解释的意思是一样的...但是为什么可以这样呢..--《白话01背包》
#include<stdio.h>
#define MAX 12881
int dp[MAX];
int w[MAX]，va[MAX];
int main()
{
int N,M;
int i,j;
scanf("%d%d",&N,&M);
for(i=1;i<=N;i++)
scanf("%d%d",&w[i],&va[i]);
for(i=1;i<=N;i++)
for(j=M;j>=jewelry[i][0];j--)
if(dp[j]<dp[j-w[i]]+va[i])
dp[j]=dp[j-w[i]]+va[i];
printf("%d\n",dp[M]);
return 0;
}
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
poj3628Bookshelf 2 牛的书架
分析：（很是重要呀...）
首先，这是一个比较简单的01背包问题...你可以把这样想：对于这个”背包“，我们要选的”物品“（牛），将它们的“价值”和“重量”都看成相等的，即牛的高度，然后就是确定什么作为背包... 哎哎不知道有没有人和我一样，最开始一直在想，把架子的高度作为”背包“，怎么老是WA.....请看这句话 This total height must be no less than the height of the bookshelf in order for
the cows to reach the top. 其实吧....题意不是在不超过梯子的高度下选几头牛让其高度最大....而是选择几头牛，在所有的组合超过梯子高度的情况下选择超过的最少的那一个方案.....
于是..这样的话那就可以把所有的牛的高度加起来 的sum作为背包容量....然后dp一次...
状态转移方程为：
dp[j]=max(dp[j],dp[j-h[i]]+h[i]);表示把第i头牛跌起来的最大高度，h[i]表示第i头牛的高度
要注意的是，最后的dp[sum]并不是最终的选择，因为这里是要选择超过梯子的最小高度...
那么最后可以用一个for循环找一次
#include <stdio.h>
#include <string.h>
int dp[1000005],a[22];
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
int i,j,sum = 0;
memset(dp,0,sizeof(dp));
memset(a,0,sizeof(a));
for(i = 1; i<=n; i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
for(i = 1; i<=n; i++)
for(j = sum; j>=a[i]; j--)
dp[j] = max(dp[j],dp[j-a[i]]+a[i]);
for(i = 1; i<=sum; i++)//这里就是找超过梯子高度最下的那个
{
if(dp[i]>=m)
{
printf("%d\n",dp[i]-m);//答案是差值
break;
}
}
}
return 0;
}
然后还有就是可以用dfs，不过多解释...给出代码
#include<stdio.h>
#define MAX 20
#define IF 20000005
int N,B;
int sum;
int ans;
int cow[MAX];
void dfs(int n,int va)
{
if(n == N)
{
if(va>=B && va<ans)ans=va;
return;
}
dfs(n+1,va);//这里实际是枚举每次要不放、要不不放牛的情况...
dfs(n+1,va+cow[n]);
}
int main()
{
while(~scanf("%d%d",&N,&B))
{
sum=0;
ans=IF;
for(int i=0;i<N;i++)
scanf("%d",&cow[i]),sum+=cow[i];
dfs(0,0);
printf("%d\n",ans-B);
}
return 0;
}
----------------------------------------------------------------------------------------------------------------------------
hdu1864最大报销额
相信看到题目的人都大概知道要用01背包解决，不过也相信有很多地方很恼人...比如：
题目说：每张发票上，单项物品的价值不得超过600元，其实却是单类物品，意思是你得先把一张发票的每一项分类求和 ,A类sum_A，以及B_sum,C_sum....然后判断条件就是 三者之和不超过1000，每类不超过600,
其次，你若用发票最大报销额 max 作为背包...那么dp[max].....很难表示。因为这是一个double类型的数，强制转换为 int 有可能有误差。....
还有就是，一张发票中出现了别的类型的物品，那么整张发票就不能报销.
所有要注意以上几点。
于是...就看了别人的结题报告....发现有一个很巧妙的手法....在平时..我们dp的过程都是用 背包的容量去正向或者反向dp....在这里...看到前辈们居然。。。。直接上代码...附有详细说明：
还要说明的一点是，这里，我们把每一张能报销的发票看做一个物品..
#include<stdio.h>
#include<string.h>
int N;发票数
double Q;最大报销额
double thing[31];//发票数组
int thing_sum;//统计能报销的发票数
double dp[31];//dp过程中的数组，
double a,b,c;//三类物品的和
void Input()//读入
{
int m;//每张发票的物品数
char ch;//物品类
double pre;//每次物品的价格
for(int i=0;i<N;i++)
{
scanf("%d",&m);
bool flag=true;//用来判定是不是出现其他类别的物品
a=b=c=0;
while(m--)
{
scanf(" %c:%lf",&ch,&pre);//这里的%c前面有一个空格，这样就按格式输入..不要担心空格换行被ch吸收
if(ch=='A') a+=pre;
else if(ch=='B') b+=pre;
else if(ch=='C') c+=pre;
else flag=false; //出现其他种类..标记
}
if(a+b+c<=1000 && flag &&(a<=600 && b<=600 && c<=600))//单类不超过600、总和、无其他类物品
thing[thing_sum++]=a+b+c;
}
}
void work()//处理
{
int i,j;
double max;//临时计算
double ans=0;//保存结果
memset(dp,0,sizeof(dp));
for(i=0;i<thing_sum;i++)//这里还是和平时的dp差不多...
{
max=0;
for(j=0;j<i;j++)//但是这里就有技巧啦。表示，我们取前i-1件物品，挑选其中价值最大的，并且和第i件报销之和不超过最大限制
{
if(dp[j]>max && dp[j]+thing[i]<=Q)
max=dp[j];
}
dp[i]=max+thing[i];//在这里dp[i]任然表示前i张发票能报销的最大金额
if(dp[i]>ans)//在这个过程中，用ans保存最大的...
ans=dp[i];
}
printf("%.2lf\n",ans);//over啦////太神奇啦...
}
int main()
{
while(scanf("%lf%d",&Q,&N),N)
{
Input();
work();
}
return 0;
}
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
poj3211洗衣服
啧啧...觉得一开始应该有很多人难明白题意吧。。。大意：
很多件衣服，给两个情侣洗，值得注意的是衣服可以有很多件，每一件颜色可以相同也可以不同，但是，为了不让衣服相互染色，他们两个必须一起洗完一种颜色的衣服，才可以一起洗另一种颜色的衣服，就算有一个颜色的衣服只有一件，也得让一个洗完，(另一个旁边看着他洗
)，才可以一起处理下一种颜色，要求让时间最少，
分析：
那么就只能对于每一种颜色去01背包dp一次，比如对于红色衣服有N件，每一件的时间我们知道，那么意思就是要求我们把这N件衣服分给这两个人洗，可以知道，分配的越均匀，那么一起完成的时间就会越少，那么我们可以选择这N件衣服的时间和 sum的 1/2 做为背包，挑出其中几件衣服，让它们的时间和不超过sum/2，并且最接近sum/2 ，那么...对于前面的分析就有 01背包的味道啦。然后 把这dp[sum/2]的衣服时间给女孩洗(出于好男人的选择而已，因为这个值是不超过sum/2
的时间，也就是少的时间)，另一个的时间就是sum-dp[sum/2]......（注意这个时间是完成这个颜色的总时间，这个不会有问题吧？）
像这样，把所有的颜色dp一次，保存每次的 sum-dp[sum/2]和...就是答案
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
#define MAX 101
struct node
{
int time;
string color;
bool operator <(const node &n)const
{
if(color==n.color)//只要按照颜色排序就可以
return time<n.time;
else
return color<n.color;
}
}head[MAX];
int M,N;
void Input()
{
int i;
string str;
for(i=0;i<M;i++)
cin>>str;
for(i=0;i<N;i++)
cin>>head[i].time>>head[i].color;
sort(head,head+N);
}
void dp()
{
int ans=0;
for(int i=0;i<N;)//这里我们用j更新i变量
{
int j=i+1;
int sum=head[i].time;
while(head[j].color == head[i].color && j<N)//选取颜色相同的物品
{
sum+=head[j].time;
j++;
}
//开始一种颜色dp
int DP[MAX*1000]={0};
for(int p=i;p<j;p++)
for(int q=sum/2;q>=head[p].time;q--)
if(DP[q]<DP[q-head[p].time]+head[p].time)
DP[q]=DP[q-head[p].time]+head[p].time;
ans+=sum-DP[sum/2];
i=j;
}
printf("%d\n",ans);
}
int main()
{
while(~scanf("%d%d",&M,&N),N+M)
{
Input();
dp();
}
return 0;
}
以后做了在更新
个人愚昧观点，欢迎指正和讨论