如题：如何写一个完全背包算法。需要打印出取的那些物品，分别取了几次
有编号分别为a,b,c,d,e的N=5件物品，它们的重量w分别是2,2,6,5,4，它们的价值v分别是6,3,5,4,6，他们的体积是c分别是3,5,2,6,4，现在给你个承重为M=10，体积是15的背包。算出最优的组合，物品可以重复放入背包
public class test {
static int V = 15;
static int W = 10;
static int N = 5;
static int[] values = { 6, 3, 5, 4, 6 };
// static int[] volume = { 3, 5, 2, 4, 6 };
static int[] volume = { 10, 5, 2, 6, 4 };
static int[] weights = { 2, 2, 6, 5, 4 };
static int[][][] pack = new int[W + 1][V + 1][N];// 定义包裹,pack[1][2][3]表示重量为1，容量为2的包裹里放了多少个物品4（物品以0索引）
static int[][] value = new int[W + 1][V + 1];// 定义包裹价值,value[1][2]表示重量为1，容量为2的包裹的最大价值
public static void main(String[] args) {
for (int i = 0; i < W + 1; i++) {// 遍历重量
for (int j = 0; j < V + 1; j++) {// 遍历容量
if (i == 0 || j == 0) {// 如果重量或者容量为0
value[i][j] = 0;// 包裹的最大价值为0
} else {// 否则
value[i][j] = value[i][j - 1];// 初始化包裹价值等于同重量容量小一的包裹
pack[i][j] = pack[i][j - 1];
for (int k = 0; k < N; k++) {// 遍历物品
if ((i >= weights[k]) && (j >= volume[k])) {// 如果包裹装的下该物品
if (value[i - weights[k]][j - volume[k]] + values[k] > value[i][j]) {// 如果装下该物品后，剩下的空间取最优选择，所得的总和价值如果大于之前的包裹价值
pack[i][j] = pack[i - weights[k]][j - volume[k]].clone();// 包裹装填该物品
pack[i][j][k]++;// 包裹装填该物品
value[i][j] = value[i - weights[k]][j - volume[k]] + values[k];// 更新包裹价格
}
}
}
}
}
}
String str = "最大价值是" + value[W][V];// 打印最大价值
System.out.println(str);
for (int i = 0; i < N; i++) {// 打印包裹物品情况
str = "第" + (i + 1) + "个物品的数量是" + pack[W][V][i];
System.out.println(str);
}
}
}
允许重复挑选，数值有很大的时候可以用贪心法，以减小空间复杂度。
public class test {
static int V = 32291; // 背包所承载的最大容量
static int W = 64582; // 背包所承载的最大重量
static int N = 3; // 物品数目
static double[] values = { 24078.6, 17640, 5716.48 }; // 每个物品的价值
static int[] volume = { 2450, 2450, 1540 }; // 每个物品的体积
static int[] weights = { 13230, 8820, 2464 }; // 每个物品的重量
static int[] pack = new int[N];// 定义包裹
static double value = 0;// 定义包裹价值
static int Vtmp = V;
static int Wtmp = W;
public static void main(String[] args) {
while (true) {
double maxV = 0;
int k = 0;
for (int i = 0; i < N; i++) {
int num;
if (Vtmp / volume[i] > Wtmp / weights[i]) {
num = Wtmp / weights[i];
} else {
num = Vtmp / volume[i];
}
if (maxV < num * values[i]) {
maxV = num * values[i];
k = i;
}
}
if (maxV == 0) {
break;
}
Vtmp -= volume[k];
Wtmp -= weights[k];
value += values[k];
pack[k]++;
}
String str = "最大价值是" + value;// 打印最大价值
System.out.println(str);
for (int i = 0; i < N; i++) {// 打印包裹物品情况
str = "第" + (i + 1) + "个物品的数量是" + pack[i];
System.out.println(str);
}
}
}
package com.leetcode;
public class Csdn {
/**
* 有编号分别为a,b,c,d,e的N=5件物品，它们的重量w分别是2,2,6,5,4，
* 它们的价值v分别是6,3,5,4,6，他们的体积是c分别是3,5,2,6,4，现在给你个承重为M=10，
* 体积是15的背包。算出最优的组合，物品可以重复放入背包
*/
public static int V = 15; // 背包所承载的最大容量
public static int W = 10; // 背包所承载的最大重量
public static int N = 5; // 物品数目
public static int[] values = { 6, 3, 5, 4, 6 }; // 每个物品的价值
public static int[] volume = { 10, 5, 2, 6, 4 }; // 每个物品的体积
public static int[] weights = { 2, 2, 6, 5, 4 };// 每个物品的重量
public static int[][][] pack = new int[W + 1][V + 1][N];// 定义包裹,pack[1][2][3]表示重量为1，容量为2的包裹里放了多少个物品4（物品以0索引）
public static int[][] value = new int[W + 1][V + 1];// 定义包裹价值,value[1][2]表示重量为1，容量为2的包裹的最大价值
public static void main(String[] args) {
for (int i = 0; i < W + 1; i++) {// 遍历重量
for (int j = 0; j < V + 1; j++) {// 遍历容量
if (i == 0 || j == 0) {// 如果重量或者容量为0
value[i][j] = 0;// 包裹的最大价值为0
} else {// 否则
value[i][j] = value[i][j - 1];// 初始化包裹价值等于同重量容量小一的包裹
for (int k = 0; k < N; k++) {// 遍历物品
if ((i >= weights[k]) && (j >= volume[k])) {// 如果包裹装的下该物品
if (value[i - weights[k]][j - volume[k]] + values[k] >= value[i][j]) {// 如果装下该物品后，剩下的空间取最优选择，所得的总和价值如果大于之前的包裹价值
pack[i][j] = pack[i - weights[k]][j - volume[k]].clone();// 包裹装填该物品
pack[i][j][k]++;// 包裹装填该物品
value[i][j] = value[i - weights[k]][j - volume[k]] + values[k];// 更新包裹价格
}
}
}
}
}
}
String str = "最大价值是" + value[W][V];// 打印最大价值
System.out.println(str);
for (int i = 0; i < N; i++) {// 打印包裹物品情况
str = "第" + (i + 1) + "个物品的数量是" + pack[W][V][i];
System.out.println(str);
}
}
}
计算每个商品在剩余空间内的最大数量
循环第一个商品从0到max
递归调用剩下商品
这个算法就是将弄出了所有商品和数量的集合然后取最大,然后就是商品属性是不固定数量的可以在data.txt加减对代码没有影响
不说了上代码
data.txt
商品,价值,重量,体积
0,0,10,15
a,6,2,10
b,3,2,5
c,5,6,2
d,4,5,6
e,6,4,4
代码
package com.cab.pack.demo;
import com.alibaba.fastjson.JSON;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.List;
/**
* @author: lanyanhua
* @date: 2021/8/2 7:37 下午
* @Description:
*/
public class PackTest {
public List<Label> labels = new ArrayList<>();//特征标签
public List<Goods> goodsAttrs = new ArrayList<>();//商品属性
public static void main(String[] args) {
PackTest test = new PackTest();
test.getData("/Users/lanyanhua/Downloads/demo/src/main/resources/data/data.txt");
//总量
List<Integer> counts = new ArrayList<>();
for (int i = 2; i < test.labels.size(); i++) {
counts.add(test.labels.get(i).count);
}
List<Detailed> res = test.baseList(test.goodsAttrs, counts);
//结果输出
System.out.println(JSON.toJSONString(res));
System.out.println();
for (int i = 2; i < test.labels.size(); i++) {
Label label = test.labels.get(i);
System.out.println("背包"+label.label + ":" + label.count);
}
System.out.println("可最大价值：" + test.v(res));
System.out.println("名称\t数量\t价值\t明细总量");
for (Detailed d : res) {
Goods goods = d.goods;
System.out.print(goods.name + "\t" + d.number + "\t" + d.value+"\t");
//明细
for (int i = 0; i < goods.attrs.size(); i++) {
System.out.print(test.labels.get(i + 2).label + ":" + goods.attrs.get(i) * d.number+"\t");
}
System.out.println();
}
}
/**
* 最佳清单
*
* @param goodsList 商品列表
* @param count 剩余容量
* @return 最佳清单
*/
public List<Detailed> baseList(List<Goods> goodsList, List<Integer> count) {
Goods goods = goodsList.get(0);
//获取当前商品从 0到最大存放数量对应的剩余容量
List<List<Integer>> counts = goodsMaxNum(goods.attrs, count);
if (counts.size() == 0) {
//已经放不下了
return new ArrayList<>();
}
//商品只剩余一种直接计算最大可存放数量
if (goodsList.size() == 1) {
//结束递归 名称 数量 价值
List<Detailed> baseList = new ArrayList<>();
//size-1 0下标对应的商品也是0个不算
int number =counts.size()-1;
baseList.add(new Detailed(goods, number, goods.value * number));
return baseList;
}
//最佳清单
List<Detailed> baseList = null;
//后面的商品
List<Goods> goods1 = goodsList.subList(1, goodsList.size());
//0 - maxNum 表示当前商品装了几个
for (int i = 0; i < counts.size(); i++) {
Detailed detailed = new Detailed(goods, i, goods.value * i);
//获取容量
List<Integer> count1 = counts.get(i);
//计算后面商品的最佳清单
List<Detailed> temp = baseList(goods1, count1);
//数量大于1添加到清单
if (i > 0) {
temp.add(detailed);
}
//大于替换
if (baseList == null || v(temp) > v(baseList)) {
baseList = temp;
}
}
return baseList;
}
public int v(List<Detailed> list) {
return list.stream().mapToInt(i -> i.value).sum();
}
/**
* 商品数量(下标)剩余容量（List<Integer>）的关系
*
* @param attrs 商品属性
* @param count 剩余容量
*/
public List<List<Integer>> goodsMaxNum(List<Integer> attrs, List<Integer> count) {
List<List<Integer>> res = new ArrayList<>();
//取最大存放数量
int max = getMax(attrs, count);
if(max==0){
return new ArrayList<>();
}
//i 商品数量
for (int i = 0; i <= max; i++) {
List<Integer> countTemp = new ArrayList<>();
//遍历每个属性
for (int i1 = 0; i1 < attrs.size(); i1++) {
//i个商品的属性值
Integer a = i * attrs.get(i1);
//剩余值
countTemp.add(count.get(i1) - a);
}
res.add(countTemp);
}
return res;
}
/**
* 取当前商品最大数量
*
* @param attrs 属性
* @param count 剩余数量
* @return 最大值
*/
public int getMax(List<Integer> attrs, List<Integer> count) {
int max = -1;
for (int i = 0; i < attrs.size(); i++) {
int temp = count.get(i) / attrs.get(i);
if (max == -1 || temp < max) {
max = temp;
}
}
return max;
}
private void getData(String path) {
String str;
try {
FileInputStream fis = new FileInputStream(path);
InputStreamReader isr = new InputStreamReader(fis, StandardCharsets.UTF_8);
BufferedReader in = new BufferedReader(isr);
//标签
str = in.readLine();
String[] label = str.split(",");
str = in.readLine();
String[] count = str.split(",");
for (int i = 0; i < label.length; i++) {
labels.add(new Label(label[i], Integer.valueOf(count[i])));
}
//商品数据
while ((str = in.readLine()) != null) {
//数据处理
String[] split = str.split(",");
Goods goods = new Goods();
goods.name = split[0];
goods.value = Integer.parseInt(split[1]);
List<Integer> attrs = new ArrayList<>();
for (int i = 2; i < split.length; i++) {
attrs.add(Integer.parseInt(split[i]));
}
goods.attrs = attrs;
goodsAttrs.add(goods);
}
in.close();
} catch (Exception e) {
throw new RuntimeException("读取数据文件失败！" + e.getMessage());
}
}
public static class Label {
//标签
public String label;
//总量
public Integer count;
public Label(String label, Integer max) {
this.label = label;
this.count = max;
}
}
public static class Detailed {
//商品
public Goods goods;
//数量
public int number;
//价值
public int value;
public Detailed(Goods goods, int number, int value) {
this.goods = goods;
this.number = number;
this.value = value;
}
}
public static class Goods {
//名称
public String name;
//价值
public int value;
//属性
public List<Integer> attrs;
}
}
```