我该如何解决？ KnapSack - 值相同，但每个对象都有三个权重 [英] How can I solve it? KnapSack - values all the same but each other object has three weights

问题描述

我有一个解决我的练习的问题。我读了关于动态编程和算法，我认为我的练习是具体的背包问题。我用蛮力的方式解决了这个问题，但是我无法用动态程序来解决它。

我有一个重量为300吨的船（背包）。有晶体本身有3种物质（X，Y，Z） - 每种物质都有重量，所有晶体都具有相同的值。我需要包装尽可能多的晶体，但是所有填充晶体的物质的比例必须是1：1：1。但是，例如，如果我有三个比例为1：1：1的晶体，它们给出最大数量的吨和八个晶体，这些晶体具有相同的吨数（晶体的两个其他组合给出最大的吨数），我需要选择使用最少数量的晶体的组合。

我用强力方法解决了 - 我创建了所有组合的数组列表。接下来我发现他们以1：1：1的比例组合。接下来，我发现最大数量的结晶，晶体数量最少（如果有两个或更多个相同的最大吨数的组合）。我检查了测试，它返回了很好的分数，
我不知道如何用动态编程解决它/ /有人帮助我吗？

例如，当我有10个水晶时：

  1）X = 2 Y = 3 Z = 4 
 2）X = 5 Y = 10 Z = 2 
 3）X = 3 Y = 3 Z = 3 
 4）X = 1 Y = 0 Z = 6 
 5）X = 9 Y = 12 Z = 4 
 6）X = 1 Y = 1 Z = 1 
 7）X = 2 Y = 1 Z = 0 
 8）X = 1 Y = 2 Z = 3 
 9）X = 1 Y = 1 Z = 1 
 10）X = 4 Y = 3 Z = 3 
 
解决方案
是：最多27吨五颗晶体（数字：1,3,6,7和9）
解决方案
互联网上有一些很好的教程，可以彻底解释背包问题。
 
 
 
更具体地说，我建议这个具体的一个，其中完全解释问题和DP方法，包括使用三种不同语言（包括Java）的解决方案。
  //针对0-1背包问题的动态编程解决方案
 class K napsack 
 {
 //返回最大两个整数的效用函数
 static int max（int a，int b）{return（a> B）？ a：b } 
 
 //返回可以放在背包容量中的最大值W 
 static int knapSack（int W，int wt []，int val []，int n）
 {
 int i，w; 
 int K [] [] = new int [n + 1] [W + 1]; 
 
 //从底部向上构建表K [] [] 
 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]; 
} 
 
 //上面测试的驱动程序
 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））; 
} 
} 
 / *此代码由Rajat Mishra提供* / 
  
 
 $ b $来源： GeeksForGeeks  
 
I have a problem with solve my exercise. I read about dynamic programming and algorithms and I think my exercise is "specific knapsack problem". I solved it with brute force method but I can't solve it with dynamic programming.

I have a ship (knapsack) which has 300 tons of weight. There are crystals which have in themselves 3 substances (X, Y, Z) - each other substance has weight and all crystals have the same value. I need to pack to ship as many as possible crystals but the proportions of substances of all packed crystals must be 1:1:1. But for example if I have three crystals with proportions 1:1:1 which give the biggest number of tons and eight crystals which give the same number of tons (two other combinations of crystals give the biggest number of tons) I need to choose the combinations with the lowest number of crystals.

I solved it with brute force method - I created a list of arrays of all combinations. Next I found they combinations with 1:1:1 proportions. Next I found the combination which gives the biggest number of tons and has the lowest number of crystals (if there are two or more combinations with the same biggest number of tons). I checked tests and it returned good scores,
I haven't any idea how can I solve it with dynamic programming ;/ Is there someone who help me? 

For Example when I have 10 crystals: 
 1) X =2 Y =3 Z =4
 2) X =5 Y=10 Z =2
 3) X =3 Y =3 Z =3
 4) X =1 Y =0 Z =6
 5) X =9 Y=12 Z =4
 6) X =1 Y =1 Z =1
 7) X =2 Y =1 Z=0
 8) X =1 Y =2 Z =3
 9) X =1 Y =1 Z =1
10) X =4 Y =3 Z =3
The solution is: max 27 tons with five crystals (numbers: 1, 3, 6, 7 and 9)
解决方案
There are a few good tutorials on the internet that explain the Knapsack problem thoroughly.

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 */
Source: GeeksForGeeks

                        
这篇关于我该如何解决？ KnapSack  - 值相同，但每个对象都有三个权重的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！