Welcome to my blog, I’m glad to meet you here! I hope you can feel a relaxed and pleasant atmosphere here, where you can not only obtain interesting content and knowledge, but also speak freely and share your thoughts and insights.
- Recommended: kuan’s homepage, keep learning, keep summarizing, make progress together, live and learn
- Navigation
- Tan Yue Sword Points to Big Factory Series: Comprehensive summary of core Java technology points, such as collections, jvm, concurrent programming redis, kafka, Spring, microservices, Netty, etc.
- Common development tool series: List of commonly used development tools, such as IDEA, Mac, Alfred, electerm, Git, typora, apifox, etc.
- Database series: Detailed summary of commonly used database MySQL technical points, as well as MySQL problems encountered in work, etc.
- Lazy man’s operation and maintenance series: Summarize useful commands, wouldn’t it be nice to free your hands? It can be completed with one command and never requires two operations
- Data structure and algorithm series: summarize data structure and algorithm, different types of targeted training, improve programming thinking, and target big manufacturers
I look forward to exploring, learning and growing with you in this small online world. Welcome to subscribe to this column
Blog Directory
-
-
-
- 1.Problem description
- 2. Problem analysis
- 3. Two-dimensional solution
- 4. One-dimensional solution
- 5. Continue to optimize
-
-
1.Problem description
The 0-1 Knapsack Problem is a classic combinatorial optimization problem that usually appears in computer science and mathematics. The context is that you are given a set of items, each item has a specific weight and value, and a backpack with a fixed capacity. The goal of the problem is to determine which items should be selected to put in the backpack so that their total weight does not exceed the capacity of the backpack and their total value is maximized.
The 0-1 knapsack problem is called a 0-1 because for each item, you have only two choices: either put it in the knapsack (denoted as 1) or not put it in the knapsack (denoted as 0). An item cannot be partially placed in a backpack.
2. Problem analysis
/*
1. n items are all solid and have weight and value.
2. Now you have to take away items not exceeding 10 grams
3. You can take nothing or take everything every time. Ask what the highest value is.
No. Weight (g) Value (Yuan) Abbreviation
1 4 1600 gold piece 400 A
2 8 2400 One ruby 300 R
3 5 30 a piece of silver S
4 1 1_000_000 One diamond D
1_001_630 Greedy solution
1_002_400 Correct solution
*/
/*
0 1 2 3 4 5 6 7 8 9 10
0 0 0 0 0 A A A A A A A gold
1 0 0 0 0 A A A A R R R Ruby
2 0 0 0 0 A A A A R R R Silver
3 0 D D D D DA DA DA DA DR DR Diamond
if(cannot fit) {
dp[i][j] = dp[i-1][j]
} else { can fit it
dp[i][j] = max(dp[i-1][j], item.value + dp[i-1][j-item.weight])
}
*/
3. Two-dimensional solution
static class Item {<!-- -->
int index;
String name;
int weight;
int value;
public Item(int index, String name, int weight, int value) {<!-- -->
this.index = index;
this.name = name;
this.weight = weight;
this.value = value;
}
@Override
public String toString() {<!-- -->
return "Item(" + name + ")";
}
}
public static void main(String[] args) {<!-- -->
Item[] items = new Item[]{<!-- -->
new Item(1, "Gold", 4, 1600),
new Item(2, "Gem", 8, 2400),
new Item(3, "Silver", 5, 30),
new Item(4, "Diamond", 1, 10_000),
};
System.out.println(select(items, 10));
}
static int select(Item[] items, int total) {<!-- -->
int[][] dp = new int[items.length][total + 1];
print(dp);
final Item item0 = items[0];
for (int j = 0; j < total + 1; j + + ) {<!-- -->
if (j >= item0.weight) {<!-- -->//can fit
dp[0][j] = item0.value;
}
}
print(dp);
for (int i = 1; i < items.length; i + + ) {<!-- -->
final Item item = items[i];
for (int j = 0; j < total + 1; j + + ) {<!-- -->
if (j >= item.weight) {<!-- -->//can fit
dp[i][j] = Integer.max(dp[i - 1][j], item.value + dp[i - 1][j - item.weight]);
} else {<!-- -->
dp[i][j] = dp[i - 1][j];
}
}
print(dp);
}
return dp[items.length - 1][total];
}
static void print(int[][] dp) {<!-- -->
System.out.println(StringUtil.repeat(" " + "-", 20));
Object[] array = IntStream.range(0, dp[0].length + 1).boxed().toArray();
System.out.printf((StringUtil.repeat("] ", dp[0].length)) + "%n", array);
for (int[] d : dp) {<!-- -->
array = Arrays.stream(d).boxed().toArray();
System.out.printf((StringUtil.repeat("] ", d.length)) + "%n", array);
}
}
4. One-dimensional solution
static class Item {<!-- -->
int index;
String name;
int weight;
int value;
public Item(int index, String name, int weight, int value) {<!-- -->
this.index = index;
this.name = name;
this.weight = weight;
this.value = value;
}
@Override
public String toString() {<!-- -->
return "Item(" + name + ")";
}
}
public static void main(String[] args) {<!-- -->
Item[] items = new Item[]{<!-- -->
new Item(1, "Gold", 4, 1600),
new Item(2, "Gem", 8, 2400),
new Item(3, "Silver", 5, 30),
new Item(4, "Diamond", 1, 10_000),
};
System.out.println(select(items, 10));
}
static int select(Item[] items, int total) {<!-- -->
int[] dp = new int[total + 1];
System.out.println(Arrays.toString(dp));
final Item item0 = items[0];
for (int j = 0; j < total + 1; j + + ) {<!-- -->
if (j >= item0.weight) {<!-- -->//can fit
dp[j] = item0.value;
}
}
System.out.println(Arrays.toString(dp));
for (int i = 1; i < items.length; i + + ) {<!-- -->
final Item item = items[i];
for (int j = total; j > 0; j--) {<!-- -->
if (j >= item.weight) {<!-- -->//can fit
dp[j] = Integer.max(dp[j], item.value + dp[j - item.weight]);
}
}
System.out.println(Arrays.toString(dp));
}
return dp[total];
}
5. Continue optimization
static class Item {<!-- -->
int index;
String name;
int weight;
int value;
public Item(int index, String name, int weight, int value) {<!-- -->
this.index = index;
this.name = name;
this.weight = weight;
this.value = value;
}
@Override
public String toString() {<!-- -->
return "Item(" + name + ")";
}
}
public static void main(String[] args) {<!-- -->
Item[] items = new Item[]{<!-- -->
new Item(1, "Gold", 4, 1600),
new Item(2, "Gem", 8, 2400),
new Item(3, "Silver", 5, 30),
new Item(4, "Diamond", 1, 10_000),
};
System.out.println(select(items, 10));
}
static int select(Item[] items, int total) {<!-- -->
int[] dp = new int[total + 1];
for (int i = 0; i < items.length; i + + ) {<!-- -->
final Item item = items[i];
for (int j = total; j > 0; j--) {<!-- -->
if (j >= item.weight) {<!-- -->//can fit
dp[j] = Integer.max(dp[j], item.value + dp[j - item.weight]);
}
}
System.out.println(Arrays.toString(dp));
}
return dp[total];
}
Note: The inner loop needs to be in reverse order, otherwise the result of dp[j – item.weight] will be overwritten in advance
If you find it useful, please give it a like
.
My level is limited, if there are any mistakes, you are welcome to comment, criticize and correct me!If you think this article is helpful to you, please give it a like and save it. Thank you very much!
Stay Hungry Stay Foolish The road is long and difficult, but the journey is about to begin. Let’s work hard together!
