最近又做了不少背包的题目(其实时很久前做的一直懒得写解题报告……)，比初学时接触了更多的题型。
比较水的题放在一起总结下。
Hdu 1864 最大报销额
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1864
题意：中文题。题目描述很坑爹，单项不超过600应该是单种不超过600，也就是2 A:500 A:200这种发票也是不行的。
思路：0—1背包，把每张发票当一个物品， 其中，发票中有单种大于600的或者总额大于1000的，这张发票扔掉不要，也就是不加入物品的行列。每张发票的费用和价值均为1，dp[j-1]+data[i]<=Q为附加选取条件，状态转移方程dp[j]=max(dp[j],dp[j-1]+data[i]);因为有附加选取条件，所以dp[top]不一定是最优解，需要遍历整个dp数组。网上还有一种用钱数当背包的做法，个人感觉效率不高。
#include <iostream>
#include <cstdio>
#include <cstring>
#define max(a,b) ((a)>(b)?(a):(b))
int top,n;
double dp[35],data[35];
double Q;
void Input ()
{
top=0;
char str[15],ch;
for (int i=0;i<n;i++)
{
int cas;
bool flag=false;
double a,b,c,temp;
scanf("%d",&cas);
a=b=c=0;
for (int j=1;j<=cas;j++)
{
scanf("%s",str);
sscanf(str,"%c:%lf",&ch,&temp);
if (ch=='A')
a+=temp;
else if (ch=='B')
b+=temp;
else if (ch=='C')
c+=temp;
else //不属于ABC三类则该发票不考虑
flag=true;
}
if (flag)
continue;
if (a>600 || b>600 || c>600 || a+b+c>1000)
continue;
data[top++]=a+b+c;
}
}
int main ()
{
while (scanf("%lf%d",&Q,&n),n)
{
memset(dp,0,sizeof(dp));
Input ();
for (int i=0;i<top;i++) //背包容量为top,每张发票费用为1
for (int j=top;j>=1;j--)
if (dp[j-1]+data[i]<=Q)
dp[j]=max(dp[j],dp[j-1]+data[i]);
double ans=0;
for (int k=0;k<=top;k++)
ans=max(ans,dp[k]);
printf("%.2lf\n",ans);
}
return 0;
}
Poj 2392 Space Elevator
题目链接：http://poj.org/problem?id=2392
题意:奶牛们要用K个不同类型的石头建太空电梯.每一种石头的高度为Hi，数量为Ci,且不能放在高于Ai的地方,求最高能建多高的太空电梯.
思路：多重背包。有一点贪心的思想，将Ai小的放在下面会更优.所以先排序.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)<(y)?(x):(y)
int dp[40010];
struct Data
{
int h,a,c;
bool operator < (const Data& _b) const
{
return a<_b.a;
}
}data[405];
void ZeroOnePack (int cost, int weight,int limit)
{
for (int j=limit;j>=cost;j--)
dp[j] = max(dp[j], dp[j-cost] + weight);
}
void CompletePack (int cost, int weight,int limit)
{
for (int j=cost;j<=limit;j++)
dp[j] = max(dp[j], dp[j-cost] + weight);
}
void MultiplePack (int cost, int weight, int all,int limit)
{
if (cost*all >= limit) //如果足够,转化为完全背包
{
CompletePack (cost, weight,limit);
return ;
}
int k=1;
while (k < all) //否则利用二进制的思想将其划分为若干个小物品
{
ZeroOnePack (k*cost, k*weight,limit);
all-=k;
k<<=1;
}
ZeroOnePack (all*cost,all*weight,limit);
}
int main ()
{
#ifdef ONLINE_JUDGE
#else
freopen("read.txt","r",stdin);
#endif
int k,i;
while (~scanf("%d",&k))
{
int v=0;
memset(dp,0,sizeof(dp));
for (i=1;i<=k;i++)
{
scanf("%d%d%d",&data[i].h,&data[i].a,&data[i].c);
v=max(v,data[i].a);
}
sort (data+1,data+k+1);
for (i=1;i<=k;i++)
MultiplePack (data[i].h,data[i].h,data[i].c,data[i].a);
int ans=-1;
for (i=0;i<=v;i++)
ans=max(ans,dp[i]);
printf("%d\n",ans);
}
return 0;
}
/*
3
7 40 3
5 23 8
2 52 6
2
99 396 4
100 398 2
Out
48
398
10
*/
Poj 1276 Cash Machine
题意：有各种不同面值的货币,每种面值的货币有不同的数量,要求要你找出不超过cash的最大钱数。
思路：多重背包模板题，费用和价值相同
#include <cstdio>
#include <cstring>
#define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)<(y)?(x):(y)
int n,sum,v;
int dp[100005];
void ZeroOnePack (int cost, int weight)
{
for (int j=v;j>=cost;j--)
dp[j] = max(dp[j], dp[j-cost] + weight);
}
void CompletePack (int cost, int weight)
{
for (int j=cost;j<=v;j++)
dp[j] = max(dp[j], dp[j-cost] + weight);
}
void MultiplePack (int cost, int weight, int all)
{
if (cost*all >= v) //如果足够,转化为完全背包
{
CompletePack (cost, weight);
return ;
}
int k=1;
while (k < all) //否则利用二进制的思想将其划分为若干个小物品
{
ZeroOnePack (k*cost, k*weight);
all-=k;
k<<=1;
}
ZeroOnePack (all*cost,all*weight);
}
int cost[12],num[12];
int main ()
{
#ifdef ONLINE_JUDGE
#else
freopen("read.txt","r",stdin);
#endif
while (~scanf("%d%d",&v,&n))
{
int i;
memset(dp,0,sizeof(dp));
for (i=1;i<=n;i++)
scanf("%d%d",&num[i],&cost[i]);
for (i=1;i<=n;i++)
MultiplePack (cost[i],cost[i],num[i]);
printf("%d\n",dp[v]);
}
return 0;
}
Hdu 3033 I love sneakers!
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3033
题意：Iserlohn 要买运动鞋，商店总共有n双运动鞋Iserlohn喜欢，他总共有m元钱，这些运动鞋分为k类，没类都有自己的编号id，单价price，对Iserlohn的价值value。Iserlohn想每一类运动鞋至少买一双，在不超过他所拥有的总金额前提下，使他得到的value最大。
思路：分组+01背包。首先，这是一个01背包，即每件物品最多只能拿一次。增加的限制在于每类物品至少拿一个。程序的第一步首先将同一类的物品放在一起。我们用f[i][j]表示前i类物品组成j的代价所取得的最大价值。设有K类物品，背包的容量为V，则答案就是f[K][V]。
枚举第i类中的每一件物品，由于每一件物品最多只能拿一次，那么递推时显然应该按照01背包一样逆着递推，
对于当前枚举的类i和当前枚举的第i类中的物品j以及当前枚举的背包的容量k（也就是我们求f[i][k]），
设其费用和价值分别为cost和val，f[i][k]=max(f[i-1][k-cost]+val,f[i][k-cost]+val)，前者表示到目前为止i类中的物品只取j，后者表示i类中的物品除了j之后还可以取其他的。
#include <cstdio>
#include <iostream>
#include <cstring>
#define max(a,b) ((a)>(b)?(a):(b))
int dp[11][10005];
int w[105],cost[105],id[105];
int n,v,m;
int main ()
{
while (~scanf("%d%d%d",&n,&v,&m))
{
int i;
for (i=1;i<=n;i++)
scanf("%d%d%d",&id[i],&cost[i],&w[i]);
memset(dp,0,sizeof(dp));
for (i=1;i<=m;i++)
{
for (int k=1;k<=n;k++)
if (id[k]==i)
for (int j=v;j>=cost[k];j--)
dp[i][j]=max(dp[i][j],max(dp[i][j-cost[k]]+w[k],dp[i-1][j-cost[k]]+w[k]));
}
if (dp[m][v]>0)
printf("%d\n",dp[m][v]);
else
printf("Impossible\n");
}
return 0;
}
Hdu 1712 ACboy needs your help
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1712
题意：有n门课程，m天时间，若花j天去学i这门课，可以得到价值a[i][j]。求可以获得的最大价值。
思路：分组+01背包。和上题思路差不多，区别是每门课最多只能复习一次，也可以不复习。设f[i][j]表示用前j天复习前i门课（可能只是i门中的某几门）的最大价值。
f[i][j]=max(f[i-1][j],f[i-1][j-k]+val[i][k]),val[i][k]表示用k天复习第i门课的价值。然后再用01背包的一维数组表示，就得到代码中的状态转移方程
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
int a[103][103];
int dp[103];
int main ()
{
#ifdef ONLINE_JUDGE
#else
freopen("read.txt","r",stdin);
#endif
int n,m;
while (~scanf("%d%d",&n,&m),n||m)
{
int i,j;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
scanf("%d",&a[i][j]);
memset(dp,0,sizeof(dp));
for (i=1;i<=n;i++)
for (j=m;j>=0;j--)
for (int k=1;k<=j;k++)
dp[j]=max(dp[j],dp[j-k]+a[i][k]);
printf("%d\n",dp[m]);
}
return 0;
}
Poj 1837 Balance
题目链接：http://poj.org/problem?id=1837
非常好的一道背包题，这篇文章分析的很好，我就不多写了：http://blog.csdn.net/lyy289065406/article/details/6648094
#include <cstdio>
#include <iostream>
#include <cstring>
int c,g;
int h[25],w[25];
//int dp[20][15*25*20*2+5];
int dp[2][15*25*20*2+5];
int main ()
{
#ifdef ONLINE_JUDGE
#else
freopen("read.txt","r",stdin);
#endif
while (~scanf("%d%d",&c,&g))
{
int i;
for (i=1;i<=c;i++)
scanf("%d",&h[i]);
for (i=1;i<=g;i++)
scanf("%d",&w[i]);
memset(dp,0,sizeof(dp));
dp[0][7500]=1;
// dp[i][ j+ w[i]*c[k] ]= ∑(dp[i-1][j]) 状态转移方程
/* for (i=1;i<=g;i++) //循环方法一
for (int k=1;k<=c;k++)
for (int j=0;j+w[i]*h[k]<=15000;j++)
dp[i][ j+w[i]*h[k] ]+=dp[i-1][j];
for (i=1;i<=g;i++) //循环方法二
for (int j=0;j<=15000;j++)
if (dp[i-1][j]) //只有之前达到过的状态才处理,否则忽略,可大幅提高运行速度
for (int k=1;k<=c;k++)
dp[i][ j+w[i]*h[k] ]+=dp[i-1][j];*/
for (i=1;i<=g;i++) //循环方法二滚动数组优化
{
int t=i&1;
for (int j=0;j<=15000;j++)
if (dp[t^1][j])
for (int k=1;k<=c;k++)
dp[t][ j+w[i]*h[k] ]+=dp[t^1][j];
memset(dp[t^1],0,sizeof(dp[t^1]));
}
printf("%d\n",dp[g&1][7500]);
}
return 0;
}