首页 > 代码库 > 01背包

01背包

01背包是动态规划中,最基础也是经典的一个算法之一。

经典题意:

1.有n个不同的物体,有体积为m的一个背包;

2.n个物体分别有自己的体积v,价值c;

 

输出:

在背包中能装的最大价值

 

题解:

首先将这n个物体的体积和价值存在两个不同的数组中(v[i],表示第i个物体的体积,c[i]表示第i个物体的价值)

  01背包的动态规划方程为:f[i, j]=max( f[i-1 ,j] ,f[i-1, j-v[i]]+c[i]);f[i, j]表示在前 i 件物体中选择若干件放在容量为 j 的背包中可以取得的最大价值。

所以问题就在于第 i 件物品该不该放在背包中。

一维的具体代码:

 1 int dp[maxn];
 2 int c[maxn];
 3 int v[maxn];
 4 
 5 for (int i = 0; i < n; i++)
 6 {
 7     for (int j = m; j >= v[i]; j--)
 8     {
 9         dp[j] = max(dp[j], dp[j - v[i]] + c[i]);
10     }
11 }

二维的具体代码:

 1 int dp[m + 1][maxn] = { 0 };
 2 int c[maxn];
 3 int v[maxn];
 4 
 5 for (int i = 0; i < n; i++)
 6 {
 7     for (int j = m; j >= 0; j--)//此时正序,逆序皆可,因为有i的存在
 8     {
 9         if (j >= v[i])
10             dp[i + 1][j] = max(dp[i][j], dp[i][j - v[i]] + c[i]);
11         else
12             dp[i + 1][j] = dp[i][j];
13     }
14 }

 

但是有时候题目会变态的问你选择了哪些物体,或者说是选择了哪些路径。参考下位大佬的博客:

http://blog.csdn.net/wumuzi520/article/details/7014559

01背包