您现在的位置是:首页 > 后台技术 > 数据结构与算法数据结构与算法
动态规划算法解决背包问题(图文)
第十三双眼睛2023-10-22【数据结构与算法】人已围观
简介动态规划算法解决背包问题
package com.xingchen.day016; public class Package { public static void main(String[] args) { int[] w = {1,4,3}; int[] val = {1500,3000,2000}; int m = 4; int n = w.length;//物品的个数 //为了记录放入商品的情况,创建一个二维数组 int[][] path = new int[n + 1][m + 1]; //创建一个二维数组 int[][] v = new int[n + 1][m + 1]; //初始化第一行和第一列 for (int i= 0 ;i < v.length;i++) { v[i][0] = 0; } for (int i = 0;i <v[0].length;i++) { v[0][i] = 0; } for (int i=1;i<v.length;i++) { for (int j = 1; j<v[0].length;j++) { if (w[i-1] > j) { v[i][j] = v[i-1][j]; } else { //v[i][j] = Math.max(v[i-1][j],val[i-1] + v[i-1][j-w[i-1]]); //为了记录商品存放到背包的情况,不能直接的使用公式,需要用ifelse来体现 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[i][j] = 1; } else { v[i][j] = v[i-1][j]; } } } } for (int i=0;i<v.length;i++) { for (int j = 0;j<v[0].length;j++) { System.out.print(v[i][j] +" "); } System.out.println(""); } int i = path.length - 1; int j = path[0].length - 1; while (i> 0 && j> 0) { if (path[i][j] == 1) { System.out.printf("第%d个商品放入背包", i); j -= w[i-1]; } i--; } } } |
Tags:
很赞哦! ()
上一篇:分治算法汉诺塔(图文)
下一篇:字符串暴力匹配(图文)