package DynamicProgramming;/*** A DynamicProgramming based solution for 0-1 Knapsack problem*/public class Knapsack {private static int knapSack(int W, int wt[], int val[], int n) throws IllegalArgumentException {if(wt == null || val == null)throw new IllegalArgumentException();int i, w;int rv[][] = new int[n + 1][W + 1]; //rv means return value// Build table rv[][] in bottom up mannerfor (i = 0; i <= n; i++) {for (w = 0; w <= W; w++) {if (i == 0 || w == 0)rv[i][w] = 0;else if (wt[i - 1] <= w)rv[i][w] = Math.max(val[i - 1] + rv[i - 1][w - wt[i - 1]], rv[i - 1][w]);elserv[i][w] = rv[i - 1][w];}}return rv[n][W];}// Driver program to test above functionpublic static void main(String args[]) {int val[] = new int[]{50, 100, 130};int wt[] = new int[]{10, 20, 40};int W = 50;int n = val.length;System.out.println(knapSack(W, wt, val, n));}}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。