01背包问题:
有N件物品和一个容量为v的背包。第i件物品的体积(质量)是volume[i],价值是value[i]。求解将哪些物品装入背包可使价值总和(dp[ ])最大。
01背包的特点就是:每种物品仅有一件,可以选择放或不放。
核心代码:dp[i][v]=max(dp[i-1][v],dp[i-1][v-c[i]]+w[i])
理解:现在需要放置的是第i件物品,这件物品的体积(质量)是c[i],价值是w[i],
因此f[i-1][v]代表的就是不将这件物品放入背包,
f[i-1][v-c[i]]+w[i]则是代表将第i件放入背包之后的总价值,
比较两者的价值,得出最大的价值存入现在的背包之中。
模板例题:
[HDU - 2602](https://vjudge.net/problem/17434/origin)代码:
#include<algorithm>
#include<string.h>
#include<stdio.h>
using namespace std;
int dp[1005], volume[1010], value[1010];
int main()
{
int i, j, n, v, k;
scanf("%d", &k);
while(k--)
{
memset(dp,0,sizeof(dp));
memset(value,0,sizeof(value));
memset(volume,0,sizeof(volume));
scanf("%d%d", &n, &v);
for(i=1; i<=n; i++)
{
scanf("%d", &value[i]);
}
for(i=1; i<=n; i++)
{
scanf("%d", &volume[i]);
}
for(i=1; i<=n; i++)
{
for(j=v; j>=volume[i]; j--)
{
if(dp[j]<dp[j-volume[i]]+value[i])
{
dp[j]=dp[j-volume[i]]+value[i];
}
}
}
printf("%d\n", dp[v]);
}
return 0;
}
模板:
for(i=1; i<=n; i++)
{
for(j=v; j>=volume[i]; j--)
{
if(dp[j]<dp[j-volume[i]]+value[i])
{
dp[j]=dp[j-volume[i]]+value[i];
}
}
}
01背包路径查找模板题
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
struct node
{
int volume, value;
int id;
} v[10010];
int dp[10010], pre[100][10010];
int res[10010];
int main()
{
int cnt=1;
int T;
scanf("%d", &T);
while(T--)
{
int n, m;
scanf("%d%d", &n, &m);
memset(pre,0,sizeof(pre));
memset(dp,0,sizeof(dp));
memset(v,0,sizeof(v));
memset(res,0,sizeof(res));
for(int i=1; i<=m; i++)
{
scanf("%d%d", &v[i].value, &v[i].volume);
v[i].id=i;
}
for(int i=1; i<=m; i++)
for(int j=n; j>=v[i].volume; j--)
if (dp[j-v[i].volume]+v[i].value > dp[j])
{
dp[j]=dp[j-v[i].volume]+v[i].value;
pre[i][j]=1;
}
int sum1=0, sum2=0, k=0;
for(int i=m,j=n; i>0; i--)
{
if(pre[i][j]==1)
{
sum1+=v[i].value;
sum2+=v[i].volume;
res[k++]=v[i].id;
j-=v[i].volume;
}
}
printf("Case #%d:\n", cnt++);
printf("%d %d\n", sum1, sum2);
sort(res, res+k);
for(int i=0; i<k; i++)
{
if(i!=0) printf(" ");
printf("%d", res[i]);
if(i==k-1) printf("\n");
}
}
return 0;
}
网友评论