您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

动态规划算法解决背包问题(图文)

第十三双眼睛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：

很赞哦！ ()

上一篇：分治算法汉诺塔(图文)

下一篇：字符串暴力匹配(图文)