Определенный алгоритм ранцевания

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 */ 

Источник: GeeksForGeeks