【算法设计与分析】— —实现最优载的贪心算法

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 v = new Vector();
		v.add(t1);
		v.add(t2);
		v.add(t3);
		v.add(t4);
		v.add(t5);
		// 按重量排序
		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("选中的编号为：");
		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 + "]";
	}
 
}

#include 
 
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("选中的编号为：\n");
    for (int i = 0; i < size; i++) {
        if (v[i].Wi + w <= Weight) {
            w += v[i].Wi;
            printf("%d\n", v[i].x);
        }
    }
 
    return 0;
}

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]
 
# 按重量排序
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("选中的编号为：")
for i in range(5):
    if v[i].Wi + w <= Weight:
        w += v[i].Wi
        print(v[i].x)

#include 
#include 
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 v;
    v.push_back(t1);
    v.push_back(t2);
    v.push_back(t3);
    v.push_back(t4);
    v.push_back(t5);
 
    // 按重量排序
    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 << "选中的编号为：" << 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;
}