8.7 贪心策略例题---背包问题（最优装载问题、部分背包问题）

本文主要是介绍8.7 贪心策略例题---背包问题（最优装载问题、部分背包问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题1：最优装载问题（简单）

代码：


import java.util.Arrays;
import java.util.Scanner;public class Main {/* */public static void main(String[] args) {//（1）输入相关数据Scanner sc = new Scanner(System.in);int n = sc.nextInt();//物体数int c = sc.nextInt();//总重量不超过cint[] w = new int[n];//每个物体重量for(int i=0;i<n;i++) {w[i] = sc.nextInt();}//(2)排序Arrays.sort(w);//（3）选取尽量多的物品f(w,c);}private static void f(int[] w, int c) {int sum=0;int cnt=0;for(int i=0;i<w.length;i++) {sum+=w[i];if(sum<=c) {cnt++;}else {break;}}System.out.println(cnt);}}

问题2：部分背包问题

每个物体可以只取走一部分: 即如果选取某物品之后总重量超过C，不选则小于C，故只需选择C所需的那一部分。

输入：

第一行：物体总数n 总重量不超过C

接下来n行：每个物体的重量、价值

输出：

最大总价值

代码：


import java.util.Arrays;
import java.util.Scanner;public class Main {/* * 思路：（1）将每个物体的价值和重量封装在对象中，并按照单位重量的价值排序。单位重量的价值 = 物体价值/重量*             （2）从后向前，每次选取单位价值最大的物体*    (3)如果选取物体i后，总重量超过C，则选取其中的一部分，该部分的价值=C还需的重量*该物体的单位重量价值*/public static void main(String[] args) {//（1）输入相关数据Scanner sc = new Scanner(System.in);int n = sc.nextInt();//物体数int c = sc.nextInt();//总重量不超过cObj[] objs = new Obj[n];for(int i=0;i<n;i++) {//输入每个物体的重量和价值objs[i] = new Obj(sc.nextInt(),sc.nextInt());}//(2)排序Arrays.sort(objs);//（3）选取总价值尽量高的物品getRes(objs,c);}private static void getRes(Obj[] objs, int c) {double maxvalue = 0;//记录总价值int weight=0;//记录当前已有的重量for(int i=objs.length-1;i>=0;i--) {int w = objs[i].w;int v = objs[i].v;if((weight+w)<=c) {//加上当前物体的重量不超过cmaxvalue+=v;//价值累加weight+=w;//重量累加}else {//加上当前物体的重量超过c，则取一部分double p = objs[i].getPrice(v, w);maxvalue+=(c-weight)*p;break;}}//forSystem.out.println(maxvalue);}private static class Obj implements Comparable<Obj>{int w;//重量int v;//价值public Obj(int w, int v) {super();this.w = w;this.v = v;}public double getPrice(int v,int w) {//获取单位重量的价值return v/(double)w;}@Overridepublic int compareTo(Obj o) {//比较单位重量的价值double x = this.getPrice(this.v, this.w)-o.getPrice(o.v, o.w);if(x==0) return 0;else if(x<0) return -1;else return 1;}}
}