背包问题可以使用动态规划获得最优解，动态规划的思路是：通过获得单阶段的最优解后，升级到多阶段，每次升级时都使用上一阶段的最优解计算，避免遍历所有可能时产生的时间消耗。动态规划解背包问题时，需要借助二维数组的表格。表格的行为所有物品，表格的列为步长递增至背包总容量，步长是优化二维数组表格的方法，取所有物品体积的最大公约数可以使表格中的无用列最少。对应表格[行，列]的数据为，当前物品列前（包括当前物品）的所有物品选择放入背包时的最大价值。每新计算一行时，需要判断如果当前行的物品在背包为空的情况下可以放入时，剩余空间可以放的最大价值，这里就需要参考上一行的数据，这也就是动态规划的算法应用处。如果当前物品可以放入且剩余容量放入获得的最大价值加当前物品的最大价值大于上一行同一列的值时，更新当前列，否则使用上一行对应列的值填充。动态规划最终建立的二维表格的数据会根据行的物品顺序有所差异，但是最优解是同一个，就是二维表的最后一行的最好一列。
package test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
/**
* Created by saishangmingzhu on 2018/11/27.
*/
public class Rucksack {
//【1】输入背包容量
//【2】输入物品体积及价值
public static void main(String[] arg) {
new Rucksack().dynamic();
}
/**
* 动态规划
【1】定义表格，物品体积的最大公约数作为列的步长求出最短列，物品作为行
【2】定义物品，名称、体积、价值
*/
public void dynamic(){
int rucksackV=10;
List
int i=0;
goodsList.add(i++,new Goods("0",0,0));//方便构建表格使用，无业务意义
//测试最大公约数为1的情况
goodsList.add(i++,new Goods("书",1,2));
goodsList.add(i++,new Goods("足球",3,4));
goodsList.add(i++,new Goods("大箱子",7,2));
goodsList.add(i++,new Goods("macbook",3,6));
goodsList.add(i++,new Goods("iphone",1,5));
goodsList.add(i++,new Goods("礼盒",5,3));
goodsList.add(i++,new Goods("小箱子",4,2));
// //测试最大公约数为2的情况
// goodsList.add(i++,new Goods("书",2,2));
// goodsList.add(i++,new Goods("足球",4,4));
// goodsList.add(i++,new Goods("大箱子",8,2));
// goodsList.add(i++,new Goods("macbook",6,6));
int step=getGCD(goodsList,rucksackV);
//表格中第0行，第0列无业务意义，使用的意义是不需要在后续表格使用中判断坐标越界，用空间换时间
int colum=rucksackV/step+1;
int[][] table=new int[i][colum];
for (int m=1;m
int worth=goods.getWorth()+table[m-1][surplus/step];
if (worth>table[m-1][n]){
table[m][n]=worth;
}
}
}
}
for (int m=1;m
int minV=rucksackV;
int[] vs=new int[goodsList.size()-1];//-1为去除没有业务意义的第一个
for (int i=0;i
for (int v:vs){
if(v%minV!=0){
flag=false;
break;
}
}
if (flag){
break;
}
minV--;
}
return minV;
}
}
class Goods{
private String name;
private int volume;
private int worth;
public Goods(){}
public Goods(String n,int v,int w){
this.name=n;
this.volume=v;
this.worth=w;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getVolume() {
return volume;
}
public void setVolume(int volume) {
this.volume = volume;
}
public int getWorth() {
return worth;
}
public void setWorth(int worth) {
this.worth = worth;
}
}0daybank
文章评论