39.动态规划算法
2022/1/17 1:03:34
本文主要是介绍39.动态规划算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
public static void main(String[] args) { // TODO Auto-generated method stub int[] w = {1, 4, 3};//物品的重量 int[] val = {1500, 3000, 2000}; //物品的价值 这里val[i] 就是前面讲的v[i] int m = 4; //背包的容量 int n = val.length; //物品的个数 //创建二维数组, //v[i][j] 表示在前i个物品中能够装入容量为j的背包中的最大价值 int[][] v = new int[n+1][m+1]; //为了记录放入商品的情况,我们定一个二维数组 int[][] path = new int[n+1][m+1]; //初始化第一行和第一列, 这里在本程序中,可以不去处理,因为默认就是0 for(int i = 0; i < v.length; i++) { v[i][0] = 0; //将第一列设置为0 } for(int i=0; i < v[0].length; i++) { v[0][i] = 0; //将第一行设置0 } //根据前面得到公式来动态规划处理 for(int i = 1; i < v.length; i++) { //不处理第一行 i是从1开始的 for(int j=1; j < v[0].length; j++) {//不处理第一列, j是从1开始的 //公式 if(w[i-1]> j) { // 因为我们程序i 是从1开始的,因此原来公式中的 w[i] 修改成 w[i-1] v[i][j]=v[i-1][j]; } else { //说明: //因为我们的i 从1开始的, 因此公式需要调整成 //v[i][j]=Math.max(v[i-1][j], val[i-1]+v[i-1][j-w[i-1]]); //v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]); //为了记录商品存放到背包的情况,我们不能直接的使用上面的公式,需要使用if-else来体现公式 if(v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) { v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]]; //把当前的情况记录到path path[i][j] = 1; } else { v[i][j] = v[i - 1][j]; } } } } //输出一下v 看看目前的情况 for(int i =0; i < v.length;i++) { for(int j = 0; j < v[i].length;j++) { System.out.print(v[i][j] + " "); } System.out.println(); } System.out.println("============================"); //输出最后我们是放入的哪些商品 //遍历path, 这样输出会把所有的放入情况都得到, 其实我们只需要最后的放入 // for(int i = 0; i < path.length; i++) { // for(int j=0; j < path[i].length; j++) { // if(path[i][j] == 1) { // System.out.printf("第%d个商品放入到背包\n", i); // } // } // } //动脑筋 int i = path.length - 1; //行的最大下标 int j = path[0].length - 1; //列的最大下标 while(i > 0 && j > 0 ) { //从path的最后开始找 if(path[i][j] == 1) { System.out.printf("第%d个商品放入到背包\n", i); j -= w[i-1]; //w[i-1] } i--; } }
这篇关于39.动态规划算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求