首页 > 代码库 > 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背包
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。