Рюкзак Оптимальное решение (грубая сила)

Question

Пользователь вводит порог веса, количество объектов, вес и стоимость трех объектов. Выход должен быть диаграммой Рюкзак, и он должен отображать оптимальное решение.

Вес должен быть максимальным, а стоимость должна быть минимальной.

Пример вывода:

w=60 
n=3 
w = 10 
w2 = 35 
w3 = 30 
c=8 
c1=4 
c2=7 

output: 
A 10 8 
B 35 4 
C 30 7 
AB 45 12 
AC 40 15 
BC 65 11 
ABC 75 19 

OPTIMAL SOLUTION: AB with total weight of 45 and total cost of 12. 

Моя проблема заключается мое оптимальное решение является неправильным. Он выводит OPTIMAL SOLUTION: A with total weight of 40 and total cost of 15.

Как его исправить?

Спасибо!

import java.util.*; 
public class KnapsackBruteForce { 
    static int numObject; 
    static int weightThreshold = 0; 
    static String variables[] = new String[100]; 
    static double numCombination; 
    static KnapsackBruteForce knapsack = new KnapsackBruteForce(); 
    static Scanner input = new Scanner(System.in); 
    public static void main(String args[]){ 
     System.out.print("Enter weight threshold: "); 
     weightThreshold = input.nextInt(); 
     System.out.print("Enter number of objects: "); 
     numObject = input.nextInt(); 

     int weightObject[] = new int[numObject+1]; 
     int costObject[] = new int[numObject+1]; 

     System.out.println("Enter variables: "); 
     for(int i=0;i<numObject;i++){ 
      variables[i] = input.next(); 
     } 
     for(int i=0;i<numObject;i++){ 
      System.out.print("Enter weight of object "+variables[i]+": "); 
      weightObject[i] = input.nextInt(); 
     } 
     for(int i=0;i<numObject;i++){ 
      System.out.print("Enter cost of object "+variables[i]+": "); 
      costObject[i] = input.nextInt(); 
     } 

     knapsack.possibleCombinations(variables, weightObject, costObject, weightThreshold, numObject); 
    } 

    public void possibleCombinations(String variables[], int weightObject[], int costObject[], int weightThreshold, int numObject){ 
     int weight = 0; 
     int cost = 0; 
     int optWeight = 0; 
     int optCost = 0; 
     String optVar = ""; 
     String newVar = ""; 

     for (int i = 1; i < (1 << numObject); i++) { 
      String newVariable = Integer.toBinaryString(i); 

      for (int j = newVariable.length() - 1, k = numObject - 1; j >= 0; j--, k--) { 
       if (newVariable.charAt(j) == '1') { 
        newVar = variables[k]; 
        weight += weightObject[k]; 
        cost += costObject[k]; 
        System.out.print(newVar); 
       } 
      } 

      System.out.println("\t" + weight + "\t" + cost); 

      if (weight <= weightThreshold) { 
       if (optWeight == 0 && optCost == 0) { 
        optWeight = weight; 
        optCost = cost; 
       } else if (optWeight <= weight) { 
        if (optCost <= cost) { 
         optVar = newVar; 
         optWeight = weight; 
         optCost = cost; 
        } 
       } 
      } 

      weight = 0; 
      cost = 0; 
     } 

     System.out.println("OPTIMAL SOLUTION: " + optVar + " with total weight of " + optWeight + " and total cost of " + optCost + "."); 
    } 
} 

Answer 1

В вашей логике есть приоритетная проблема, что, если у вас есть два ребра 45 12 и 50 13 в вашем решении, какой из них вы бы выбрали?

И в результате этой неопределенности, в следующей части вы не можете выбрать:

  else if (optWeight <= weight) { 
       if (optCost <= cost) { 
        optVar = newVar; 
        optWeight = weight; 
        optCost = cost; 
       } 
      } 

Кроме того, даже в вашей логике, вы должны принять более низкую стоимость не тем выше optCost <= cost.

Если вы устраните эту двусмысленность, то часть, которую вы должны сфокусировать, - это часть, о которой я упоминал.

Также используйте ведение журнала или, по крайней мере, распечатайте некоторую информацию на консоли, чтобы увидеть, как работает ваш код.