0-1背包问题详解：如何选择物品以最大化背包价值

0-1背包问题：给定N类型的项目和带容量C的背包，项目i的重量是Wi，其值为VI。

问：您应该如何选择要加载到背包中的项目，以使加载到背包的项目的总价值是最大的？

分析每个项目后，我们只能选择或不采取两个选项。我们不能选择加载某个项目的一部分，也不能多次加载同一项目。

解决方案：声明一个大小m [n] [c]的二维阵列。 m [i] [j]表示面对第i-the项目时可以获得的最大值，背包容量为j。然后，我们可以轻松地分析M [i] [J]的计算方法。

（1）。对于J <w [i]，背包的容量不足以放下第i-phot物品，因此您只能选择不服用它。

m [i] [j] = m [i-1] [j]

（2）。对于J> = W [i]，背包容量可以放下第三件项目，因此我们需要考虑是否可以从此项目中获得更大的价值。

如果服用，m [i] [j] = m [i-1] [jw [i]] + v [i]。在这里m [i-1] [jw [i]]是指当背包容量为jw [i]时，I-1项目的最大值，这相当于为i-themit腾出w [i]的空间。

如果您不接受，m [i] [j] = m [i-1] [j]，与（1）相同

无论是否接受，这自然是这两种情况之间最有价值的比较。

从中，我们可以获得状态转移方程：

if(j>=w[i])
 m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
else
 m[i][j]=m[i-1][j];

示例：0-1背包问题。当使用动态编程算法解决0-1背包问题时，请使用二维阵列M [i] [J]存储0-1背包问题的最佳值时，当背包的剩余容量为j时，并且可选项目是i，i，i+1，...，...，n。画

值数组v = {8，10，6，3，7，2}，

重量数组W = {4，6，2，2，2，5，1}，

当背包容量C = 12时，相应的m [i] [J]数组。

0123456789111121112111200088888888888888888888888811010101011818181818141414141416161618182440669999999999919191924545045450545066699999999999999太体14141414141999999部。

如m[2][6],在面对第二件物品，背包容量为6时我们可以选择不拿，那么获得价值仅为第一件物品的价值8，如果拿，就要把第一件物品拿出来，放第二件物品，价值10，那我们当然是选择拿。m[2][6]=m[1][0]+10=0+10=10;依次类推，得到m[6][12]就是考虑所有物品，背包容量为C时的最大价值。
#include <iostream>
#include <cstring>
using namespace std;
 
 
const int N=15;
 
 
int main()
{
 int v[N]={0,8,10,6,3,7,2};
 int w[N]={0,4,6,2,2,5,1};
 
 
 int m[N][N];
 int n=6,c=12;
 memset(m,0,sizeof(m));
 for(int i=1;i<=n;i++)
 {
 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]);
 
 
 else
 m[i][j]=m[i-1][j];
 }
 }
 
 
 for(int i=1;i<=n;i++)
 {
 for(int j=1;j<=c;j++)
 {
 cout<<m[i][j]<<' ';
 }
 cout<<endl;
 }
 
 
 return 0;
}

在这一点上，我们可以确定可以获得的最大值，但是我们不确定选择哪些项目可以获得最大值。

启动另一个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] [cw [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;
}

示例：工厂预计明年将有四个新项目A，B，C和D。下表显示了每个项目WK及其投资收入VK的投资金额。总投资为30万元。如何选择一个项目以最大化总回报？

项目

结合前两个代码

#include <iostream>
#include <cstring>
using namespace std;
 
const int N=150;
 
int v[N]={0,12,8,9,5};
int w[N]={0,15,10,12,8};
int x[N];
int m[N][N];
int c=30;
int n=4;
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;
}
 
int main()
{
 
 
 memset(m,0,sizeof(m));
 for(int i=1;i<=n;i++)
 {
 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]);
 
 else
 m[i][j]=m[i-1][j];
 }
 }/*
 for(int i=1;i<=6;i++)
 {
 for(int j=1;j<=c;j++)
 {
 cout<<m[i][j]<<' ';
 }
 cout<<endl;
 }
*/
 traceback();
 for(int i=1;i<=n;i++)
 cout<<x[i];
 return 0;
}

输出X [I]数组：0111，输出M [4] [30]：22。

结论得出结论：BCD的三个项目的总回报率最大，为220,000元。

但是，该算法只能获得一个最佳解决方案，但无法获得所有最佳解决方案。