01背包问题 详细

本文主要是介绍01背包问题 详细，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

在遇见很多个dp问题的难题后，我决定要把问题搞明白，于是研究了其中最为著名的01背包问题。下面是我的一些初步的学习成果，可能还有很多纰漏或者错误，希望大家指出。

问题概述：

有一个背包，容量为V；

有以下物品，每个物品只有一件，（我觉得拿完数量成了0，没拿就是1，故称作01背包），要拿走最大价值的物品，问怎么拿。

方法一：

穷举法

这一定是最原始的方法了，把物品的所有组合都试一遍，排除其中超过背包容量限制的组合，之后找出剩下的价值最大的那个。

可以先拿1个物品，排列；之后拿两个，排列。。。。。。当拿到n个时，即使是最小重量组合方式的也放不下时，停止遍历。在他们中找出价值最大的那个组合。

方法二：

动态规划。

我们先想想拿东西时会有几种状态？两种，

1.背包容量装不下这个东西，不拿。(j>w[i])

对应表格中的状态dp[i][j]=dp[i-1][j] 

#在这里我要解释一下，i是指拿第几个物品，j代表了物品的重量，那么dp[i][j]=dp[i-1][j] 就代表了当背包的重量为j时，不拿第i个物品。

2.背包可以装下这个物品,：(j>w[i])

如此，就又会有两种情况（1）拿了不划算，

　　　　　　　　　　　（2）拿了划算,

　　　　　　　　　　　　在这里我比喻一下，小明在矿山淘宝，他背包容量有限。山中有煤块和金块，拿了煤块就不划算，拿了金块就很划算，那么他一定装满金块。

那么对于（1）情况，我们会有：

　　dp[i][j]=dp[i-1][j]，就是不拿这个东西，和上面1一样。

对于情况（2），我们会有：

　　dp[i][j]=dp[i-1][j-w(i)]+v[i]

#这里我觉得是个难点，在我写文章前也出错了。个人认为把这个东西彻底搞懂，动态规划就入门了。

#是比较拿了第i个物品后的状态和拿第i-1个东西的状态进行比较，看那个更合适。

#这里我想引申一下经济学里的机会成本（唔，如果我没有学计算机网络，估计就学经济去了）（世界上多了一个码农，少了一株韭菜），获得一个东西的成本=它的收益-选择它所放弃的东西的收益，故只有机会成本为正，才能让资源最佳配置。和这里很相似，是吧。拿第i个东西的受益和拿第dp[i-1][j-w(i)]做比较，选择收益高的。

而知道拿了每个的效益后，就可以很容易做出选择。

 1 #include<stdio.h>
 2 
 3 int w[5]={0,2,3,4,5}; //物品重量 
 4 int v[5]={0,3,4,5,6}; //物品价值 
 5 int bagV=8;              //背包空间为8 
 6 int dp[5][9]={0};     //背包里有4个可以选择的物品，4+1=5，空间为8 
 7 
 8 
 9 int max(int a,int b){
10     if(a>=b){
11         return a;
12     }
13     else return b;
14 }
15 
16 
17 
18 int main(){
19     for(int i=1;i<=4;i++){
20         for(int j=1;j<=bagV;j++){
21             if(j<w[i]){
22                 dp[i][j]=dp[i-1][j]; 
23             }
24             else{
25                 dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
26             }
27             printf("%d ",dp[i][j]);
28         }
29         printf("\n");
30     } 
31 } 

这篇关于01背包问题 详细的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！