0
Мне было интересно, были ли какие-либо конкретные вопросы и ответы на проблему с рюкзаком, что я могу ввести и изменить этот код, чтобы убедиться, что я сделал это правильно? Я пытаюсь войти в динамическое программирование и начинаю с этой проблемы, но не знаю, действительно ли он работает без ввода - я нашел несколько случаев в некоторых точках питания, и, хотя мой код выводит правильную информацию, они были довольно простые и простые случаи, поэтому я хочу убедиться, что это работает с более мясистым входом.Входы динамического программирования Knapsack
Вот мой код:
import java.util.ArrayList;
public class Knapsack {
private int numThings = 0;
public static void main(String[] args) {
(new Knapsack()).run();
}
public void run() {
ArrayList<Thing> thingList = new ArrayList<Thing>();
thingList.add(new Thing(60, 2));
thingList.add(new Thing(75, 3));
thingList.add(new Thing(90, 4));
int maxWeight = 5;
int[] vals = new int[maxWeight + 1];
vals[2] = 60;
Thing nullThing = new Thing(0,0);
Thing max;
int maxSet = 0;
for (int i = 1; i < vals.length; i++) {// lets go through weights leading up to our maximal weight
System.out.println(i);
max = nullThing;
for (Thing x : thingList) {
if ((i-x.getWeight() >= 0) && (x.getValue() + vals[i-x.getWeight()] > max.getValue() + vals[i-max.getWeight()])) {
max = x;
maxSet = 1;//here, we compare possibilities of adding items by subtracting weights from our current index and seeing which ones produce the highest values
}
}
if (maxSet == 1) {
vals[i] = max.getValue() + vals[i-max.getWeight()];
System.out.println(max.info());//if we find something that sets a highest value, we cache that info into the array for future use
}
}
System.out.println(vals[maxWeight]);
}
private class Thing {
private int value, weight;
public Thing(int v, int w) {
value = v;
weight = w;
}
public int getValue() {
return value;
}
public int getWeight() {
return weight;
}
public String info() {
return "I have a weight of "+weight+" and a value of "+ value;
}
}
}