Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

This article also participated in the “Digitalstar Project” to win a creative gift package and creative incentive money

Optimal loading problem

The optimal loading problem is essentially a simple version of the 0-1 knapsack problem

Problem description

  • A shipment of containers is to be loaded onto a ship of c deadweight, where container I has a weight of Wi
  • The optimal loading problem requires the determination to load as many containers as possible onto a ship without limiting the loading volume

Algorithm description

  • It can be solved by greedy algorithm
  • usingThe lightest load firstThe greedy selection strategy can produce the optimal solution of the optimal loading problem

Java source code

Code has detailed comments, do not understand the comments below the message

/* * * like dust */
package loading;

import java.util.Arrays;

/** * Optimal load problem (greedy algorithm) *@author ruochen
 * @version1.0 * /
public class LoadingProblem {
	private static int[] x; 

	/ * * * *@paramC Total weight *@paramW Weight per container *@paramX records whether it is loaded (1: loaded 0: not loaded) *@return* /
	public static float Loading(float c, float[] w, int[] x) {
		int n = w.length;
		Element[] d = new Element[n];
		for (int i = 0; i < n; i++) {
			/ / initialization
			d[i] = new Element(w[i], i);
		}
		Arrays.sort(d);
		// Record the optimal value
		float opt = 0;
		for (int i = 0; i < n; i++) {
			/ / initialization
			x[i] = 0;
		}
		for (int i = 0; i < n && d[i].w <= c; i++) {
			x[d[i].i] = 1;
			opt += d[i].w;
			c -= d[i].w;
		}
		return opt;
	}
	
	public static void main(String[] args) {
		float c = 10;
		float[] w = new float[] {4.2.5.1.3};
		x = new int[w.length];
		float opt = Loading(c, w, x);
		System.out.println("The optimal value is: + opt);
		System.out.println("The optimal solution is:" + Arrays.toString(x));
	}
	
	public static class Element implements Comparable<Element> {
		float w;
		int i;
		
		public Element(float w, int i) {
			this.w = w;
			this.i = i;
		}
		
		/** ** in ascending order */
		@Override
		public int compareTo(Element o) {
			if (this.w < o.w) 
				return -1;
			else if (this.w == o.w)
				return 0;
			else 
				return 1; }}}Copy the code
The optimal value is 10.0. The optimal solution is [1, 1, 0, 1, 1].Copy the code

Finally, welcome to pay attention to my personal wechat public account “Little Ape Ruochen”, get more IT technology, dry goods knowledge, hot news