特定背包算法 [英] specific Knapsack Algorithm
问题描述
我在解决特定的背包算法问题时遇到问题。有没有人给我一些提示或帮助我?我用蛮力方法解决了这个问题,但是执行时间却很长(我检查了所有可能的组合并采取了最佳解决方案-可行)。我需要通过动态编程或贪婪算法(但通过DP更好)来解决它。我读了很多,但找不到解决方法; /这是艰苦的练习。
这里是我对锻炼的描述
I have problem with solve the specific knapsack algorithm problem. Is there someone who give me some tips or help me? I solved it by Brute Force method but the execute time is very long (I checked all possible combinations and take the best solution - it works). I need to solve it by Dynamic Programming or Greedy Algorithm (but better by DP). I read about it a lot and I can't find the solution with it ;/ It is hard exercise. HERE IS description of my exercise
推荐答案
互联网上有一些很好的教程,可以彻底解释背包问题。
There are a few good tutorials on the internet that explain the Knapsack problem thoroughly.
更具体地说,我会推荐此特定的,其中完整解释了问题和DP方法,包括使用三种不同语言(包括Java)的解决方案。
More specifically, I would recommend this specific one, where the problem and the DP-approach is entirely explained, including the solution in three different languages (including Java).
// A Dynamic Programming based solution for 0-1 Knapsack problem
class Knapsack
{
// A utility function that returns maximum of two integers
static int max(int a, int b) { return (a > b)? a : b; }
// Returns the maximum value that can be put in a knapsack of capacity W
static int knapSack(int W, int wt[], int val[], int n)
{
int i, w;
int K[][] = new int[n+1][W+1];
// Build table K[][] in bottom up manner
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0)
K[i][w] = 0;
else if (wt[i-1] <= w)
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}
return K[n][W];
}
// Driver program to test above function
public static void main(String args[])
{
int val[] = new int[]{60, 100, 120};
int wt[] = new int[]{10, 20, 30};
int W = 50;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
}
}
/*This code is contributed by Rajat Mishra */
来源: GeeksForGeeks
这篇关于特定背包算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!