01背包问题c语言代码穷举，c语言背包算法

01 背包问题

问题：你有一个背包，里面有N 件物品，容量为V。第i 个项目的成本为c[i]，价值为w[i]。寻找可以装入背包的物品，以最大限度地提高总价值。

分析：

这是最基本的背包问题。它的特点是每种类型只有一个项目，并且你可以选择是否放置它。

使用子问题定义状态。即f[i][v]表示用前i个物品装满容量为v的背包所得到的最大值。在这种情况下，其状态转移方程变为：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

这个方程非常重要，基本上所有与背包旅行相关的方程都是由它推导出来的。因此，有必要对此进行详细说明。如果我们只考虑第i 件物品的策略（放入或不放入），子问题“将前i 件物品放入容量为v 的背包中”就变为如下：只有前i-1 项是相关的。如果不放入第i 件物品，则问题转化为“将前i-1 件物品放入容量为v 的背包中”，值就变成f[i-1][v] 这样：给定第i 个物品，问题转化为“将前i-1 个物品放入剩余容量为v-c[i] 的背包中。”在这种情况下获得的最大值是f[i-1][。 v-c[i]]加上放置第i个项目得到的值w[i]。

优化：

上述方法的时间复杂度和空间复杂度均为O(VN)。时间复杂度不需要优化，但空间复杂度可以优化到O。

首先，让我们考虑如何实现上述基本思想。我们需要一个主循环i=1.N，每次计算二维数组f[i][0.V]的所有值。那么，如果我们只使用一个数组f[0.V]，我们可以保证f[v] 代表我们在第i 个循环结束后定义的状态吗？ v] 由两个子问题f[i-1][v] 和f[i-1] [v-c[i]] 递归导出。你能保证f[i][v]吗？ （即当f[v]在第i个主循环中被压入时），我们是否可以得到f[i-1][v]和f[i-1][v-c[i]]的值？得到？事实上，这包括每个主循环中的f[v-c[i]] 必须按v=V [v] 的顺序推送。 [i -1][v-c[i]] 值。伪代码如下：

for i=1.N for v=V.0 f[v]=max{f[v],f[v-c[i]]+w[i]}; 代码实现：

1 /********************01背包问题********************/2 #include iostream 3 4 name 使用空间std; 5 #define INF -65536 6 const int V=1000;//定义体积最大值； 7 const int T=5;//定义产品数量。 /#define EMPTY10 int w[T]={6,8,3,9,2};//产品的价值； 11 int c[T]={400,600,500,600,900};//产品的体积( )13 条件编译表明不能输入{14 #ifdef EMPTY//15 for(int i=0;i=V;i++)//16 {17 f[i ]=0;18} 19 #else//Full必须安装20 f[0]=0;21 for(int i=1;i=V;i++)//条件表示必须存储满22 编译为{ 23 f[i]=INF;24 }25 # endif //EMPTY26 for(int i=0;iT;i++)27 {28 for(int v=V;v=c[i];v– )29 { 30 f[v]=max(f[v] ,f[v-c [i]]+w[i]);31 }32 }33 return f[V];34 }35 int main()36 { 37 int temp ;38 temp=package();39 couttempendl;40 return 0;41 }实际上有两种不同的方法来询问背包问题的最优解。有些问题需要在背包正好满的情况下得到最优解，而另一些问题则不需要背包满。区分这两个问题的一种实现方法是在初始化过程中进行区分。

对于第一个问题，需要准确填写背包，除了初始化时f[0]为0外，其他f[1.V]都设置为-，最后确保获得f。您只需将其装入背包即可获得最佳解决方案。

如果不需要装满背包，但希望价格尽可能大，则应在初始化时将所有f[0.V]设置为0。

为什么？这可以理解如下。如果背包中没有物品可以放入，则初始化后的f数组实际上处于合法状态。如果背包需要恰好装满，那么只有容量为0的背包才能“恰好装满”，而不需要值为0。对于其他容量的背包没有合法的解决方案，使它们处于未定义的状态。它们的所有值都必须是-。如果你不需要在背包里装满任何东西，那么任何容量的背包都有一个合法的解决方案：“Nothing”，而这个解决方案的值为0，所以初始值All将为0。