package com.knapsack.problem;
public class BackPack {
public static void main(String[] args) {
int m =
10;
int n =
3;
int w[] = {
3,
4,
5};
int p[] = {
4,
5,
6};
int c[][] = BackPack_Solution(m, n, w, p);
for (
int i =
0; i <=n; i++) {
for (
int j =
0; j <=m; j++) {
System.out.print(c[i][j]+
"\t");
if(j==m){
System.out.println();
}
}
}
}
/**
* @param m 表示背包的最大容量
* @param n 表示商品个数
* @param w 表示商品重量数组
* @param p 表示商品价值数组
* @param c[i][m] 前i个物体放入容量为m的背包的最大价值
* @param c[i-1][m] 前i-1个物体放入容量为m的背包的最大价值
* @param c[i-1][m-w[i]] 前i-1个物体放入容量为m-w[i]的背包的最大价值
*/
public static int[][]
BackPack_Solution(
int m,
int n,
int[] w,
int[] p) {
int c[][] =
new int[n +
1][m +
1];
for (
int i =
0; i < n +
1; i++) {
for (
int j =
0; j < m +
1; j++) {
if(i ==
0 || j ==
0)
c[i][j] =
0;
else if(w[i -
1] <= j){
if (c[i -
1][j] < (c[i -
1][j - w[i -
1]] + p[i -
1]))
c[i][j] = c[i -
1][j - w[i -
1]] + p[i -
1];
}
else
c[i][j] = c[i -
1][j];
}
}
return c;
}
}
转载请注明原文地址: https://ju.6miu.com/read-5310.html