0
올바르게 입력했는지 확인하기 위해이 코드를 입력하고 수정할 수있는 배낭 문제에 대한 특정 질문 및 답변이 있는지 궁금합니다. 나는 동적 인 프로그래밍에 착수하려고 노력하고 있지만이 문제로 시작하고 있지만 입력없이 실제로 작동하는지 알 수있는 방법이 없다. 나는 몇 가지 파워 포인트에서 몇 가지 사례를 발견했다. 코드가 정확한 정보를 출력하는 동안 그들은 꽤 귀여웠다. 기본적이고 단순한 경우이므로, 나는 이것이 더 많은 입력과 함께 작동하는지 확인하고자한다.배낭 동적 프로그래밍 입력
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;
}
}
}