Contents
P1060 开心的金明【NOIP2006PJ】
题目内容
大意：给定 m 件价格分别为 v_i，重要度为 w_i 的物品，求总钱数不超过 N 时最大的 \sum v_iw_i
解题思路
裸的 0-1 背包，直接求解即可，由于这是我写的第一个背包，所以用的是二维数组，也会方便理解一些。
#include <cstdio>
int n,m,v[30],p[30],f[30][30000];
inline int max(int a,int b){return a>b?a:b;}
int main()
{
scanf("%d %d",&n, &m);
for(int i=1;i<=m;i++)
scanf("%d %d",&v[i], &p[i]);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
if(v[i]>j)
f[i][j]=f[i-1][j];
else
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+v[i]*p[i]);
}
printf("%d\n",f[m][n]);
}
P1048 采药【NOIP2005PJ】
题目内容
大意：给出若干株草药采摘需要的时间以及他们对应的价值，求在给定时间内能采集到的最大价值，每种草药只有一株
解题思路
还是裸的 0-1 背包，但使用了滚动数组优化空间，注意第二层的循环顺序是从大到小即可。
#include <cstdio>
int f[1005],t,m,w[105],c[105];
inline int max(int x,int y){return x>y?x:y;}
int main()
{
scanf("%d %d",&t,&m);
for(int i=1;i<=m;i++)
scanf("%d %d",&w[i],&c[i]);
for(int i=1;i<=m;i++)
for(int j=t;j>=w[i];j--)
f[j]=max(f[j-w[i]]+c[i],f[j]);
printf("%d\n",f[t]);
return 0;
}
P1049 装箱问题【NOIP2001PJ]
题目内容
大意：给定一个容积为 V 的箱子，以及 n 个物品，每个物品有对应的体积，求如何选择能使得剩余空间最小，求剩余空间
解题思路
注意读题：这个是在 n 个物品中选，是 0-1 背包，不是完全背包，一开始我当成完全背包做了半天。
一样的 0-1 背包，只不过在这里所谓的价格和权值相等了都是对应的体积罢了。
#include <cstdio>
int f[20005],v,n,p[35];
inline int max(int a,int b){return a>b?a:b;}
int main()
{
scanf("%d\n%d",&v,&n);
for(int i=1;i<=n;i++)
scanf("%d",&p[i]);
for(int i=1;i<=n;i++)
for(int j=v;j>=p[i];j--)
f[j]=max(f[j],f[j-p[i]]+p[i]);
printf("%d\n",v-f[v]);
return 0;
}
P1616 疯狂的采药
题目内容
大意：和采药一样，只不过每种草药可以取无限多个
解题思路
看了背包九讲之后，知道了这是一个完全背包问题，解决他我使用了两种方法。
第一种是使用二进制优化，将一个物品拆成费用为 c_i2^k ，价值为 w_i2^k 的物品，其中 k\in{c_i2^k\leq V\mid k\in\N}。这样就成功将处理一个物品变为处理 O(\log\frac V{c_i}) 个物品，这样就可以使用 0-1 背包解决问题了。
#include <cstdio>
int t,m,f[100010],totm,w[100010],c[100010];
inline int max(int a,int b){return a>b?a:b;}
int main()
{
scanf("%d %d", &t ,&m);
totm=1;
for(int i=1;i<=m;i++)
{
int ww, cc;
scanf("%d %d", &cc, &ww);//cc is time, ww is value
for(int j=0;(1<<j)*cc<=t;j++)//读入的时候就要进行处理
{
w[totm]=ww*(1<<j);//位运算可香了
c[totm++]=cc*(1<<j);
}
}
for(int i=1;i<=totm;i++)//然后就是和 0-1 背包一模一样的处理
for(int j=t;j>=c[i];j--)
f[j]=max(f[j],f[j-c[i]]+w[i]);
printf("%d\n",f[t]);
return 0;
}
第二种就是常规的完全背包，就是将 0-1 背包的内层循环改了顺序而已，代码如下：
#include <cstdio>
int t,m,f[100010],totm,w[100010],c[100010];
inline int max(int a,int b){return a>b?a:b;}
int main()
{
scanf("%d %d",&t,&m);
for(int i=1;i<=m;i++)
scanf("%d %d",&c[i],&w[i]);
for(int i=1;i<=m;i++)
for(int j=c[i];j<=t;j++)//注意这里的顺序
f[j]=max(f[j],f[j-c[i]]+w[i]);
printf("%d\n",f[t]);
return 0;
}
留言