部分背包问题和最优装载问题【贪心算法】

部分背包问题和最优装载问题

• 部分背包问题
• 部分背包问题介绍
  首先介绍下0-1背包问题。假设一共有N件物品，第 i 件物品的价值为 Vi ，重量为Wi，一个小偷有一个最多只能装下重量为W的背包，他希望带走的物品越有价值越好，请问：他应该选择哪些物品？
  

0-1背包问题的特点是：对于某件（更适合的说法是：某类）物品，要么被带走（选择了它），要么不被带走（没有选择它），不存在只带走一部分的情况。

部分背包问题代码实现【Java】

package day1.java;

import java.util.Arrays;
import java.util.Scanner;

public class test {
    static Scanner scanner = new Scanner(System.in);

    static class item implements Comparable<item> {
        private double value = 0;
        private double weight = 0;

        public double getPrice() {
            return value/weight;
        }

        public item(int value, int weight) {
            this.value = value;
            this.weight = weight;
        }

        public int compareTo(item other) {
            if (value / weight < other.getValue() / other.getWeight())
                return 1;
            if (value / weight > other.getValue() / other.getWeight())
                return -1;
            return 0;
        }

        public double getValue() {
            return value;
        }

        public double getWeight() {
            return weight;
        }

        public void setValue(double value) {
            this.value = value;
        }

        public void setWeight(double weight) {
            this.weight = weight;
        }

    }

    public static void main(String args[]) {
        int n, m;
        n = scanner.nextInt();
        m = scanner.nextInt();
        item[] items = new item[n];
        int[] w = new int[n];
        int[] v = new int[n ];
        for (int i = 0; i < n; i++) {
            w[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            v[i] = scanner.nextInt();
            items[i] = new item(v[i], w[i]);
        }
        Arrays.sort(items);
        int i=0;
        int answer = 0;
        while(m!=0&&i<items.length){
            if(items[i].getWeight()<=m){  //当前物体能全部装下
                m-=items[i].getWeight();
                answer+=items[i].getValue();
                items[i].setWeight(0);
                i++;
            }else{
                answer+=m*items[i].getPrice();
                items[i].setWeight(items[i].getWeight()-m);
                m=0;
            }
        }
        System.out.println("背包中物品的最大价值为: "+answer);
        System.out.println("依次装入背包的物品为:");
        for(int j=0;j<items.length;j++){
            System.out.println("第"+j+"个物品："+(w[j]-items[j].getWeight())/w[j]);
        }
    }
}

结果

• 最优装载问题
• 最优装载问题介绍
  　　问题描述：有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。

对于给定的n个集装箱和轮船的载重量C，编程计算装入最多时的集装箱个数。

将古董重量由大到小排序，然后将其依次装入船中，当大于船的重量时停止，最终返回转载的数量。

最优装载问题代码实现【Java】

import java.util.Arrays;
import java.util.Scanner;

public class two {
    static Scanner scanner = new Scanner(System.in);

    static class item implements Comparable<item> {
        private int index;
        private double weight = 0;

        public item(int index, double weight) {
            this.index = index;
            this.weight = weight;
        }

        public int compareTo(item other) {
            if (weight > other.getWeight())
                return 1;
            if (weight < other.getWeight())
                return -1;
            return 0;
        }

        public double getWeight() {
            return weight;
        }

        public void setWeight(double weight) {
            this.weight = weight;
        }

        public int getIndex() {
            return index;
        }

        @Override
        public String toString() {
            return "item{" +
                    "index=" + index +
                    ", weight=" + weight +
                    '}';
        }
    }

    public static void main(String args[]) {
        int n, m;
        n = scanner.nextInt();
        m = scanner.nextInt();
        item[] items = new item[n];
        int[] w = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = scanner.nextInt();
            items[i] = new item(i, w[i]);
        }
        Arrays.sort(items);
        int i = 0;
        int answer = 0;
        while (m != 0 && i < items.length) {
            if (items[i].getWeight() <= m) {  //当前物体能全部装下
                m -= items[i].getWeight();
                answer += items[i].getWeight();
                items[i].setWeight(0);
                i++;
            }else{
                break;
            }
        }
        System.out.println("最优装载重量为: " + answer);
        System.out.println("最优装载下被选中的集装箱序号为: ");
        int []indexs=new int [n];
        int k=0;
        for (int j = 0; j < items.length; j++) {
            if(items[j].getWeight()==0)
            indexs[k++]=items[j].getIndex();
        }
        Arrays.sort(indexs);
        for (int j = n-k; j <= k; j++) {
            System.out.print(indexs[j]+" ");
        }
    }
}

结果

最优装载问题代码实现【C++】

#include 
#include 
#include 
using namespace std;
struct node
{
    int id;
    int val;
};
node box[2005];
int n,c;
bool operator <(const node &a,const node &b)
{
    return a.val<b.val;
}
void greedySelect()
{
    sort(box,box+n);
    bitset<2005> b;
    b.reset();
    for(int i=0;i<n;i++)
     if(box[i].val <= c)
     {
          b[box[i].id]=1;
          c-=box[i].val;
     }
     else break;
     cout<<b.count()<<endl;
}
int main()
{
    while(cin>>n>>c)
    {
        for(int i=0;i<n;i++)
        {
            box[i].id=i;
            cin>>box[i].val;
        }
        greedySelect();
    }
    return 0;
}

结果

输入：4 5
3 5 2 1
输出：2