输入:超市有很多种商品,让你从超市选购商品,每个品种只能选购一个,是最后都能装入承重量不超过7kg的纸袋子中,并且商品的价值最大,商品信息如下:
商品编码 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
商品名称 |
牙膏 |
啤酒 |
牛奶 |
面包 |
香皂 |
台灯 |
面粉 |
大米 |
酱油 |
纸巾 |
重量g |
300 |
500 |
200 |
250 |
250 |
1000 |
4000 |
2000 |
800 |
200 |
价值元 |
12 |
3 |
2.5 |
6 |
5 |
20 |
8 |
6 |
7 |
9 |
要求输入数据从文本文件或格式文件中导入,或程序运行时直接输入。
输出:所选商品信息形式如下
商品编码 |
商品名称 |
重量 |
价值 |
1 |
牙膏 |
300 |
12 |
2 |
啤酒 |
500 |
3 |
3 |
牛奶 |
200 |
2.5 |
4 |
面包 |
250 |
6 |
5 |
香皂 |
250 |
5 |
6 |
台灯 |
1000 |
20 |
由于时间原因,原理后续补上。。。
代码如下:
package com.ag.algorithm;
/**
* 动态规划解决0-1背包问题
*
*/
public class knapsbag {
static String[] name={"牙膏","啤酒","牛奶","面包", "香皂","台灯","面粉","大米","酱油","纸巾"};
static int[] w = {300, 500, 200, 250, 250, 1000, 4000, 2000, 800, 200};
static double[] p = {12, 3, 2.5, 6, 5, 20, 8, 6, 7, 9};
static int bagweight=7000;
static int value0=0;
static int wlen =w.length; //物品的个数
static double dp[][]=new double[wlen+1][bagweight+1]; //初始化dp数组,前i个商品的总价值;
static int[] item=new int[dp.length+1];/*用于对应name*/
public static void main(String[] args) {
findmax(w,p,bagweight);//调用方法
print();
System.out.println(findmax(w,p,bagweight));
}
/**
*
*
* 动态规划求出最大值
* @param w
* @param p
* @param bagweight
* @return
*/
private static double findmax(int[] w, double[] p, int bagweight) {
for (int i = 0; i <=w.length ; i++) {
dp[i][0]=value0;
}
for (int i = 1; i <=wlen ; i++) { //遍历物品
for (int j = 1; j <=bagweight ; j++) { //遍历背包的容量
if(j<w[i-1]){
dp[i][j]=dp[i-1][j]; //不拿物品
}else
{
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i-1]]+p[i-1]);
}
}
}
return dp[wlen][bagweight];
}
/**
* 输出商品的名字,重量和价格
*
*/
private static void print() {
System.out.println("商品编码 名称 重量 价格");
for (int i = 1; i <dp.length; i++) {
double a=item[i];
if(a==0){
System.out.println(i-1+" " + name[i-1]+" "+w[i-1]+" "+p[i-1]);
}
}
}
}