c**********e
发帖数: 2007 | 1 In an exam you have n problems to work on. i=0, 1, ..., n-1.
The i-th problem takes you x[i] minutes, and give you a score s[i].
You have 60 minutes to work on them. How can you get the best score? | c**********e
发帖数: 2007 | 2 Assumptions:
1. You do not get partial credit on a problem.
2. If you spend x[i] minutes on i-th problem, you will get the s[i] points. | p*****2
发帖数: 21240 | | x*********n
发帖数: 46 | | s******n
发帖数: 3946 | | D********g
发帖数: 650 | 6 /**
* In an exam you have n problems to work on. i=0, 1, ..., n-1.
The i-th problem takes you x[i] minutes, and give you a score s[i].
You have 60 minutes to work on them. How can you get the best score?
*/
static class DPElement {
int value;
int prevCostIdx; // 0-based cost idx
int takenThisElement; // 0/1, indicating whether taking current
element, idx 0 based.
public DPElement() {
value = 0;
prevCostIdx = 0;
takenThisElement = 0;
}
}
static void knapSackProblemSolving(final int[] x, final int[] s, final
int t) {
if (x == null || s == null || x.length == 0 || s.length == 0 || x.
length != s.length || t <= 0) {
throw new IllegalArgumentException();
}
DPElement[][] dp = new DPElement[x.length + 1][t + 1];
for (int i = 0; i < dp.length; ++i) {
for (int j = 0; j < dp[0].length; ++j) {
dp[i][j] = new DPElement();
}
}
for (int i = 1; i <= x.length; ++i) {
for (int j = 1; j <= t; ++j) {
int val = j >= x[i-1] ? s[i - 1] + dp[i-1][j-x[i-1]].value :
0;
if (x[i-1] <= j && val > dp[i-1][j].value) {
dp[i][j].value = val;
dp[i][j].prevCostIdx = j - x[i-1];
dp[i][j].takenThisElement = 1;
} else {
dp[i][j].value = dp[i-1][j].value;
dp[i][j].prevCostIdx = j;
dp[i][j].takenThisElement = 0;
}
}
}
System.out.println("Best score is " + dp[x.length][t].value);
System.out.print("Taken elements: {");
int time = t;
for (int i = x.length; i > 0; --i) {
if (dp[i][time].takenThisElement == 1) {
System.out.print("<" + (i - 1) + "," + x[i - 1] + ">");
}
time = dp[i][time].prevCostIdx;
}
System.out.println("}");
}
static void testKnapSackProblemSolving() {
int[] x = new int[] {59, 50, 10, 5, 2, 3, 58, 57, 1};
int[] s = new int[] {117, 99, 20, 10, 3, 5, 115, 114, 1};
knapSackProblemSolving(x, s, 60);
}
【在 x*********n 的大作中提到】
: Knapsack.
|
|
