data编程辅导、program程序讲解、辅导CS，c++，Java编程 解析C/C++编程|解析Java程序
- 首页 >> Java编程 Introduction
The Knapsack problem is to make the best choice among all the stuff. Assuming that the number of all the stuff is n where for the ith item, the weight is wi and value is vi. As there is a person who want to carry as much as he could, but he could only carry W pounds, where W is a round number, in his backpack. Then the problem is which object should he carry.
In this project, it needs to design a system to solve 0-1 Knapsack problem (which means for each object, it can only be carried or not and it cannot be divided) using both the Dynamic Programming method and the Greedy algorithm.
Design & Implementation
Dynamic Programming
1.Design principals
First of all, the state transformation function of the Dynamic Programming is:
f[i][v]=max{f[i-1][v],f[i-1][v-weight[i]]+value[i]}
In which f[i][v] Represents the maximum value that can be obtained by placing the previous item in a backpack with the capacity of v. Thus, this function means
that the sub-problem :"put the former i item into the backpack with the capacity of v" can be transformed into a problem involving only the former i -1 item if only the ith item is put or not put:
1)If the ith item is not put, the problem will be changed to "put the former i-1 item into the backpack with the capacity of v";
2)If the ith item is placed, the problem will be transformed into "the former i- 1 item is put into the bag with the remaining capacity of v-weight[I]". At this time, the maximum value that can be obtained is f[i-1][v-weight[I]] plus the value[I] obtained by putting the ith item into the bag.
Then the value of f[I][v] is the largest one of 1) and 2).
2.Implementation The DP part code:
Figure1. The DP code
Test
This system can give a solution for both the Dynamic Programming and the Greedy algorithm and the user of this system can also input data with keyboard by themselves.
Here is an example of test:
Figure4. the example objects
Figure5. The test result
Conclusion
In conclusion, obviously the Dynamic Programming performs better than Greedy. Actually,
the Greedy Algorithm cannot figure out the optimal solution for the 0-1 Knapsack problems well because There is no guarantee that it will eventually be able to fill the backpack, and some unused backpack space reduces the value per kilogram of backpack space. Dynamic programming algorithm has the optimal substructure property, so dynamic programming can get the optimal solution. In the greedy algorithm, every step of the greedy decision cannot be changed, because the greedy strategy is to derive the next optimal solution from the
optimal solution of the previous step, and the optimal solution before the previous step is not reserved. From the previous introduction, we can know that the greedy method is
correct condition: each step of the optimal solution must contain the optimal solution of the previous step.
The Knapsack problem is to make the best choice among all the stuff. Assuming that the number of all the stuff is n where for the ith item, the weight is wi and value is vi. As there is a person who want to carry as much as he could, but he could only carry W pounds, where W is a round number, in his backpack. Then the problem is which object should he carry.
In this project, it needs to design a system to solve 0-1 Knapsack problem (which means for each object, it can only be carried or not and it cannot be divided) using both the Dynamic Programming method and the Greedy algorithm.
Design & Implementation
Dynamic Programming
1.Design principals
First of all, the state transformation function of the Dynamic Programming is:
f[i][v]=max{f[i-1][v],f[i-1][v-weight[i]]+value[i]}
In which f[i][v] Represents the maximum value that can be obtained by placing the previous item in a backpack with the capacity of v. Thus, this function means
that the sub-problem :"put the former i item into the backpack with the capacity of v" can be transformed into a problem involving only the former i -1 item if only the ith item is put or not put:
1)If the ith item is not put, the problem will be changed to "put the former i-1 item into the backpack with the capacity of v";
2)If the ith item is placed, the problem will be transformed into "the former i- 1 item is put into the bag with the remaining capacity of v-weight[I]". At this time, the maximum value that can be obtained is f[i-1][v-weight[I]] plus the value[I] obtained by putting the ith item into the bag.
Then the value of f[I][v] is the largest one of 1) and 2).
2.Implementation The DP part code:
Figure1. The DP code
Test
This system can give a solution for both the Dynamic Programming and the Greedy algorithm and the user of this system can also input data with keyboard by themselves.
Here is an example of test:
Figure4. the example objects
Figure5. The test result
Conclusion
In conclusion, obviously the Dynamic Programming performs better than Greedy. Actually,
the Greedy Algorithm cannot figure out the optimal solution for the 0-1 Knapsack problems well because There is no guarantee that it will eventually be able to fill the backpack, and some unused backpack space reduces the value per kilogram of backpack space. Dynamic programming algorithm has the optimal substructure property, so dynamic programming can get the optimal solution. In the greedy algorithm, every step of the greedy decision cannot be changed, because the greedy strategy is to derive the next optimal solution from the
optimal solution of the previous step, and the optimal solution before the previous step is not reserved. From the previous introduction, we can know that the greedy method is
correct condition: each step of the optimal solution must contain the optimal solution of the previous step.