特定的揹包算法

Question

我有解決特定的揹包算法問題的問題。有人給我一些提示或幫助我嗎？我用Brute Force方法解決了這個問題，但執行時間非常長（我檢查了所有可能的組合並採取最佳解決方案 - 它的工作原理）。我需要通過動態編程或貪婪算法解決它（但通過DP更好）。我讀了很多，我找不到解決方案; /這是很難的練習。 HERE IS description of my exercise

HERE ARE TESTS FOR THIS EXERCISE

Answer 1

目前在互聯網上的一些好的教程，詳細解釋了揹包問題。

更具體地說，我會建議this specific one，問題出在哪裏和DP-方法完全解釋，其中包括三種不同的語言（包括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 */ 

來源：​​