01背包记录路径
01背包只能外层遍历种类,因为如果外层遍历体积,不好考察是否已经选过这个物品
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e3+10;
int n;
int m;
int v[N];
int w[N];
int f[N];
int way[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j=m;j>=v[i];j--)
{
if(f[j-v[i]]+w[i]>f[j])
{
f[j]=f[j-v[i]]+w[i];
way[i][j]=1;
}
}
}
cout<<"最值"<<endl;
cout<<f[m]<<endl;
cout<<"选择"<<endl;
for(int i=n;i>=1;i--)
{
if(way[i][m])
{
cout<<i<<endl;
m-=v[i];
}
}
}
另一种写法(一开始就f数组用二维,后面能简便一点)(另一个背景下的01背包,都一样啦)
int main()
{
int n, C, i, j, k = 0;
int temp;
printf("请输入菜的种类个数:");
scanf("%d", &n);
printf("请输入外卖报销最大的经费数额:");
scanf("%d", &C);
int Vi[n], Pi[n], MaxValue[C + 1][n + 1], a[n];
printf("请输入每种菜的量化评分:");
for (i = 0; i < n; i++)
scanf("%d", &Vi[i]);
printf("请输入与之对应的每种菜的价格:");
for (i = 0; i < n; i++)
scanf("%d", &Pi[i]);
for (i = 0; i < C + 1; i++)
MaxValue[i][0] = 0;
for (i = 0; i < n + 1; i++)
MaxValue[0][i] = 0;
for (j = 1; j <= n; j++)
{
for (i = 1; i <= C; i++)
{
if (Pi[j - 1] > i)
MaxValue[i][j] = MaxValue[j - 1][i];
else
MaxValue[i][j] = max(MaxValue[i - Pi[j - 1]][j - 1] + Vi[j - 1], MaxValue[i][j - 1]);
}
if (MaxValue[i - 1][j] != MaxValue[i - 1][j - 1])
{
a[k] = j;
k++;
}
}
printf("选择的菜的种类为: ");
for (i = 0; i < k; i++)
{
printf("第%d种 ", a[i]);
}
printf("\n");
printf("点到菜的总评价分数为: %d\n", MaxValue[C][n]);
return 0;
}
完全背包先遍历体积,和先遍历种类两种写法
种类
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j=v[i];j<=m;j++)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m]<<endl;
}
体积
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=m;i++)
{
f[i]=f[i-1];
for(int j=1;j<=n;j++)
{
if(i>=v[j])
{
// f[i]=max(f[i-v[j]]+w[j],f[i]);
if(f[i-v[j]]+w[j]>f[i])
{
f[i]=f[i-v[j]]+w[j];
way[i]=j;
}
}
}
}
cout<<f[m]<<endl;
完全背包记录路径
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e3+10;
int n;
int m;
int v[N];
int w[N];
int f[N];
int way[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=m;i++)
{
f[i]=f[i-1];
for(int j=1;j<=n;j++)
{
if(i>=v[j])
{
// f[i]=max(f[i-v[j]]+w[j],f[i]);
if(f[i-v[j]]+w[j]>f[i])
{
f[i]=f[i-v[j]]+w[j];
way[i]=j;
}
}
}
}
cout<<f[m]<<endl;
while(m>=0)
{
if(way[m])
{
cout<<way[m]<<endl;
m-=v[way[m]];
}
else m--;
}
}
/*
4 5
1 2
2 4
3 4
4 5
*/