参考：https://blog.csdn.net/xp731574722/article/details/70766804
价值数组v = {8, 10, 6, 3, 7, 2}，
重量数组w = {4, 6, 2, 2, 5, 1}，
背包容量C = 12时对应的m[i][j]数组。
0 1 2 3 4 5 6 7 8 9 10 11 12
1 0 0 0 8 8 8 8 8 8 8 8 8
2 0 0 0 8 8 10 10 10 10 18 18 18
3 0 6 6 8 8 14 14 16 16 18 18 24
4 0 6 6 9 9 14 14 17 17 19 19 24
5 0 6 6 9 9 14 14 17 17 19 21 24
6 2 6 8 9 11 14 16 17 19 19 21 24
(第一行和第一列为序号，其数值为0)
如m[2][6],在面对第二件物品，背包容量为6时我们可以选择不拿，那么获得价值仅为第一件物品的价值8，如果拿，就要把第一件物品拿出来，放第二件物品，价值10，那我们当然是选择拿。m[2][6]=m[1][0]+10=0+10=10;依次类推，得到m[6][12]就是考虑所有物品，背包容量为C时的最大价值。
给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi
int v[N]={0,8,10,6,3,7,2};
int w[N]={0,4,6,2,2,5,1};
int m[N][N]; //表示背包的价值，第i个物品时背包的重量j包含多少的价值
int n=6,c=12; //n是数量，c是重量
memset(m,0,sizeof(m));
for(int i=1;i<=n;i++)
//动态规划：子问题的解能够从前面找到（中国大学Mooc屈婉玲动态规划算法视频:https://www.icourse163.org/learn/PKU-1002525003? tid=1002695005#/learn/content?type=detail&id=1003850904&sm=1）因此数量从1开始增长，计算包含第一个物品时的最大价值
{
for(int j=1;j<=c;j++)
{
if(j>=w[i])
m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]); //能够放的下看拿上是否会获得更大价值，j-w[i]为了给第i个物品腾空，然后加上它的价值，相同的空间装的i-1个物品是否比装第i个物品更划得来
else
m[i][j]=m[i-1][j]; //因为放不下了，所以第i个物品与第I-1个物品的价值相等
}
}
到这一步，可以确定的是可能获得的最大价值，但是我们并不清楚具体选择哪几样物品能获得最大价值。
另起一个 x[ ] 数组，x[i]=0表示不拿，x[i]=1表示拿。
m[n][c]为最优值，如果m[n][c]=m[n-1][c] ,说明有没有第n件物品都一样，则x[n]=0 ; 否则 x[n]=1。当x[n]=0时，由x[n-1][c]继续构造最优解；当x[n]=1时，则由x[n-1][c-w[i]]继续构造最优解。以此类推，可构造出所有的最优解。（这段全抄算法书，实在不知道咋解释啊。。）
追踪解：
void traceback()
{
for(int i=n;i>1;i--)
{
if(m[i][c]==m[i-1][c])
x[i]=0;
else
{
x[i]=1;
c-=w[i];
}
}
x[1]=(m[1][c]>0)?1:0;
}
---------------------
作者：青龙指引你
来源：CSDN
原文：https://blog.csdn.net/xp731574722/article/details/70766804
版权声明：本文为博主原创文章，转载请附上博文链接！
网友评论