Everyone is welcome to watch my algorithm design and analysis column: Algorithm Design and Analysis_IT Yan’s Blog-CSDN Blog I hope it will be helpful to everyone!
Personal column:
Algorithm design and analysis: Algorithm design and analysis_IT Yan’s blog-CSDN blog
Java Basics: Java Basics_IT Yan’s Blog-CSDN Blog
C language: c language_IT Yan’s blog-CSDN blog
MySQL: Data Structure_IT Yan’s Blog-CSDN Blog
Data structure: Data structure_IT Yan’s blog-CSDN blog
C++: C++_IT Yan’s Blog-CSDN Blog
C51 MCU: C51 MCU (STC89C516)_IT Yan’s Blog-CSDN Blog
Webpage design and application based on HTML5: Webpage design and application based on HTML5_IT Yan’s Blog-CSDN Blog
python: python_IT Yan’s blog-CSDN blog
Welcome to watch, I hope it is useful to everyone!
Table of Contents
Purpose:
content:
Code (Java):
operation result:
Analysis of Algorithms:
Implementation of other programming languages:
C language program:
python code:
C++ code:
Purpose:
1) Understand the idea and basic principles of greedy algorithm;
2) Master the general characteristics of using greedy algorithms to solve problems;
3) Be able to correctly choose greedy strategies for practical problems;
4) Be able to prove the correctness of the algorithm for the selected greedy strategy;
5) Be able to write code correctly according to the greedy strategy;
6) Be able to correctly analyze the time complexity and space complexity of the algorithm.
Content:
A greedy algorithm for optimal loading.
Test data is available:
Assume the ship has a weight limit of 12kg
i
1
2
3
4
5
Wi(kg)
8
4
2
5
7
Code (Java):
package one;
import java.util.Vector;
public class Two {
public static void main(String[] args) {
// TODO Auto-generated method stub
thing t1 = new thing(1, 8);
thing t2 = new thing(2, 4);
thing t3 = new thing(3, 2);
thing t4 = new thing(4, 5);
thing t5 = new thing(5, 7);
Vector<thing> v = new Vector<thing>();
v.add(t1);
v.add(t2);
v.add(t3);
v.add(t4);
v.add(t5);
// Sort by weight
for (int i = 0; i < 5; i + + ) {
for (int j = 0; j < 4 - i; j + + ) {
if (v.get(j).Wi > v.get(j + 1).Wi) {
thing t = v.get(j);
v.set(j, v.get(j + 1));
v.set(j + 1, t);
}
}
}
int w = 0;
int Weight = 12;
System.out.println("The selected number is:");
for (int i = 0; i < 5; i + + ) {
if (v.get(i).Wi + w <= Weight) {
w + = v.get(i).Wi;
System.out.println(v.get(i).x);
}
}
}
}
class thing {
int x;
int Wi;
public thing(int x, int wi) {
super();
this.x = x;
Wi = wi;
}
@Override
public String toString() {
return "thing [x=" + x + ", Wi=" + Wi + "]";
}
}
Running results:
?
?Algorithm analysis:
When storing n objects,
1. Time complexity analysis:
- For the sorting operation, the bubble sorting method is used here. The outer loop loops n times, and the inner loop loops (n-1) times, (n-2) times, (n-3) times… 1 time. Therefore, the time complexity of the sorting operation is O(n + (n-1) + (n-2) + … + 1)=O(n^2).
- Loop through the elements of the vector and execute it n times. Therefore, the time complexity of this loop is: O(n^2).
To sum up: the time complexity of the entire code when storing n objects is O(n^2).
2. Space complexity analysis:
- A Vector object v is declared, which stores n thing objects. Therefore, the storage space complexity is: O(n).
- Several int type variables w, weight, and n thing objects are declared. Because the number of these variables and objects increases with the input size, the additional time complexity can be seen as O(n).
To sum up, the space complexity of the entire code to store n objects is O(n).
It should be noted that the above analysis assumes that the input size n is fixed. If the input size n increases, for example, when the number of thing objects increases, the time complexity and space complexity may change. But given a fixed input size, the time complexity of this code is O(n^2) and the space complexity is O(n). Therefore, be aware of performance issues when handling large-scale inputs.
Implementation of other programming languages:
Note: The following codes are all generated by AI. If readers find bugs, they can post them in the comment area and we will solve them together!
c language program:
#include <stdio.h>
typedef struct {
int x;
int Wi;
} Thing;
void bubbleSort(Thing arr[], int n) {
for (int i = 0; i < n; i + + ) {
for (int j = 0; j < n - i - 1; j + + ) {
if (arr[j].Wi > arr[j + 1].Wi) {
Thing temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
Thing t1 = {1, 8};
Thing t2 = {2, 4};
Thing t3 = {3, 2};
Thing t4 = {4, 5};
Thing t5 = {5, 7};
Thing v[5] = {t1, t2, t3, t4, t5};
int size = 5;
int w = 0;
int Weight = 12;
bubbleSort(v, size);
printf("The selected number is:\
");
for (int i = 0; i < size; i + + ) {
if (v[i].Wi + w <= Weight) {
w + = v[i].Wi;
printf("%d\
", v[i].x);
}
}
return 0;
}
Precautions:
- In C language, there is no direct corresponding to Java’s
Vectorclass, but an array is used.- In C language, there is no built-in bubble sort function, so you need to implement your own sorting logic.
python code:
class Thing:
def __init__(self, x, Wi):
self.x = x
self.Wi = Wi
t1 = Thing(1, 8)
t2 = Thing(2, 4)
t3 = Thing(3, 2)
t4 = Thing(4, 5)
t5 = Thing(5, 7)
v = [t1, t2, t3, t4, t5]
# Sort by weight
for i in range(5):
for j in range(4 - i):
if v[j].Wi > v[j + 1].Wi:
v[j], v[j + 1] = v[j + 1], v[j]
w = 0
Weight = 12
print("The selected number is:")
for i in range(5):
if v[i].Wi + w <= Weight:
w + = v[i].Wi
print(v[i].x)
Precautions:
- There are no strictly defined access modifiers for classes in Python, so there is no need to use the
publickeyword.- Lists in Python are represented using square brackets
[]instead ofVectorin Java.- In Python, sorting can be performed using the
sort()method of the list or thesorted()function. For simplicity here, the bubble sort algorithm is used.
C++ code:
#include <iostream>
#include <vector>
using namespace std;
class Thing {
public:
int x;
int Wi;
Thing(int x, int wi) {
this->x = x;
Wi = wi;
}
string toString() {
return "thing [x=" + to_string(x) + ", Wi=" + to_string(Wi) + "]";
}
};
int main() {
Thing t1(1, 8);
Thing t2(2, 4);
Thing t3(3, 2);
Thing t4(4, 5);
Thing t5(5, 7);
vector<Thing> v;
v.push_back(t1);
v.push_back(t2);
v.push_back(t3);
v.push_back(t4);
v.push_back(t5);
// Sort by weight
for (int i = 0; i < 5; i + + ) {
for (int j = 0; j < 4 - i; j + + ) {
if (v[j].Wi > v[j + 1].Wi) {
Thing t = v[j];
v[j] = v[j + 1];
v[j + 1] = t;
}
}
}
int w = 0;
int Weight = 12;
cout << "The selected number is:" << endl;
for (int i = 0; i < 5; i + + ) {
if (v[i].Wi + w <= Weight) {
w + = v[i].Wi;
cout << v[i].x << endl;
}
}
return 0;
}
Precautions:
- In C++, use
#includeto introduce the vector class.- In C++, use the
push_back()method to add elements to a vector.- In C++, use
coutandendlfor output.
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56303 people are learning the system