[算法]用java实现0-1背包和部分背包问题
问题描述:
0-1背包问题,部分背包问题(课本P229)
实验要求:
(1)实现0-1背包的动态规划算法求解
(2)实现部分背包的贪心算法求解
0-1背包问题代码:
public static void main(String[] args){ //获取物品个数,每个物品的重量和价值,以及背包容量 Scanner in1 = new Scanner(System.in); System.out.println("请输入物品个数和背包容量:"); int num_goods = in1.nextInt(); int capacity = in1.nextInt(); System.out.println("请输入1-"+num_goods+"的物品重量和价值:"); int[] weight = new int[num_goods+1]; int[] value = new int[num_goods+1]; Scanner in2 = new Scanner(System.in); for(int i = 1;i<=num_goods;i++){ weight[i] = in2.nextInt(); value[i] = in2.nextInt(); } in1.close(); in2.close(); //动态规划 int[][] f = new int[num_goods+1][capacity+1]; //f[i][j]表示容量为j的背包前i个物品的总价值 for(int i = 1;i<=num_goods;i++){ for(int j = 1; j<=capacity; j++){ if(weight[i] > j){ f[i][j] = f[i-1][j]; }else { int x = f[i-1][j]; int y = f[i-1][j-weight[i]] +value[i]; f[i][j] = x>y?x:y; } } } //输出结果 for(int i = 0;i<= num_goods;i++){ for(int j = 0;j<=capacity;j++){ System.out.print(f[i][j]+"\t"); if(j == capacity){ System.out.print("\n"); } } } int j = capacity; int total_value = 0; int total_weight = 0; for(int i = num_goods;i>=1;--i){ if(j>0){ if(j-weight[i] >=0){ if(f[i][j] == (f[i-1][j-weight[i]]+value[i])){ System.out.println("选取物品:"+i+"重量为:"+weight[i]+"价值为:"+value[i]); j -= weight[i]; total_value += value[i]; total_weight += weight[i]; } System.out.println("总价值为:"+total_value+"\t总重量为:"+total_weight); } } } }
二:部分背包
public class Goods{ int weight; int value; float value_per_weight; //value/weight float load; //占比系数 } //快排 public static void QuickSort(Goods []A,int l,int r){ Goods temp; int i = l; int j = r; if(l<r){ temp = A[i]; while(i != j){ while(i<j && A[j].value_per_weight <= temp.value_per_weight){ --j; } A[i] = A[j]; while(i<j && A[i].value_per_weight >= temp.value_per_weight){ ++i; } A[j] = A[i]; } A[i] = temp; QuickSort(A, l, i-1); QuickSort(A, i+1, r); } } //贪心算法 public static void Greedy(Goods[] goods,int capacity,int num_goods){ for(int i = 0; i<num_goods; i++){ if(goods[i].weight<capacity){ capacity -= goods[i].weight; goods[i].load = 1; }else if(capacity>0){ goods[i].load = ((float)capacity/(float)goods[i].weight); capacity = 0; break; } } } public static void main(String[] args){ float total_value = 0 ; float total_weight = 0; //获取物品个数,每个物品的重量和价值,以及背包容量 Scanner in1 = new Scanner(System.in); System.out.println("请输入物品个数和背包容量:"); int num_goods = in1.nextInt(); int capacity = in1.nextInt(); System.out.println("请输入1-"+num_goods+"的物品重量和价值:"); Goods[] goods = new Goods[num_goods]; Scanner in2 = new Scanner(System.in); for(int i = 0;i<num_goods;i++){ goods[i] = new part_of_package_greedy().new Goods();; goods[i].weight = in2.nextInt(); goods[i].value= in2.nextInt(); goods[i].value_per_weight = (goods[i].value)/(goods[i].weight); } in1.close(); in2.close(); QuickSort(goods,0,(num_goods-1)); //执行贪心算法 Greedy(goods, capacity, num_goods); System.out.println("执行贪心算法求得部分背包解为:"); for(int i = 0;i<num_goods;i++){ System.out.println("重量为:"+goods[i].weight+"\t价值为:"+goods[i].value+"\t装载率为:"+goods[i].load); total_value+=goods[i].value*goods[i].load; total_weight+=goods[i].weight*goods[i].load; } System.out.println("背包容量:"+capacity+"\t背包装入重量:"+total_weight+"\t装入总价值:"+total_value); }
相关推荐
lixiaotao 2019-10-28
ustbfym 2019-10-21
duyifei0 2019-06-28
算法魔功 2018-08-31
PHP100 2019-03-28
直男门诊 2018-03-22
那些年那些有趣的数学 2018-02-10
心理学哲学批判性思维 2018-01-16
VanTYS 2019-12-15
数据与算法之美 2014-05-29
ustbfym 2019-11-04
MachineIntellect 2011-08-28
程序员生涯 2018-11-08
数据与算法之美 2017-11-27
Wearabledevice 2018-08-26
fengaid 2019-03-18
yhguo00 2017-11-27
卷卷萌 2017-09-02