背包问题:
给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高
0-1 背包:
每样物品最多只能选择一次
b站这个视频讲的很详细
思路:设value[i]与weight[i]分别表示第i个物品的价值与重量,C为背包的总重量。令v[i][j]表示在前i个物品中能够装入容量为j的背包的最大价值。
当商品重量大于背包重量时,总价值即为i物品之前的总价值。
weight[i]>j时;v[i][j]=v[i-1][j]
当商品重量小于等于背包重量,背包新的总价值取下面两者最大值:
1,不取i物品的最大总价值;
2,取了i物品,i物品的价值加上,在剩余容量为(j-weight(i))中的最大价值。
v[i][j]=Math.max(v[i-1][j],value[i]+v[i-1][j-weight[i]])
//总代码:
public class Main {
public static void main(String[] args) {
int[] weight= {1,2,3,4,5};//物品的重量
int[] value= {3,4,6,8,10};//物品的价值
int capacity=10;//背包重量
int n=weight.length;//物品的种类数
f(weight,value,n,capacity);
}
public static void f(int[] weight,int[] value,int n,int capacity) {
int[][] v=new int[n+1][capacity+1];
//第一行与第一列不会用到,用零填充方便理解
//v[0][j],v[i][0]不处理默认为零
//因此v[i][j]是从1 开始算的,而weight[]与value[]是从0开始,故设计weight[]与value[]的部分需要[i-1]
for(int i=1;i<=n;i++) {
for(int j=1;j<=capacity;j++) {
if(weight[i-1]>j)//当商品重量大于背包重量时,总价值即为i物品之前的总价值。
v[i][j]=v[i-1][j];
else {
//当商品重量小于等于背包重量,背包新的总价值取下面两者最大值:
//1,不取i物品的最大总价值;
//2,取了i物品,i物品的价值加上,在剩余容量为(j-weight(i))中的最大价值。
v[i][j]=Math.max(v[i-1][j],value[i-1]+v[i-1][j-weight[i-1]]);
}
}
}
for(int i=0;i<=n;i++) {
for(int j=0;j<=capacity;j++) {
System.out.print(v[i][j]+ " ");
}
System.out.println();
}
}
}
//进一步完善
public class Main {
public static void main(String[] args) {
int[] weight= {1,2,3,4,5};//物品的重量
int[] value= {3,4,6,8,10};//物品的价值
int capacity=10;//背包重量
int n=weight.length;//物品的种类数
f(weight,value,n,capacity);
}
public static void f(int[] weight,int[] value,int n,int capacity) {
int[][] v=new int[n+1][capacity+1];
int[][] path=new int[n+1][capacity+1];
//第一行与第一列不会用到,用零填充方便理解
//v[0][j],v[i][0]不处理默认为零
//因此v[i][j]是从1 开始算的,而weight[]与value[]是从0开始,故设计weight[]与value[]的部分需要[i-1]
for(int i=1;i<=n;i++) {
for(int j=1;j<=capacity;j++) {
if(weight[i-1]>j)//当商品重量大于背包重量时,总价值即为i物品之前的总价值。
v[i][j]=v[i-1][j];
else {
//当商品重量小于等于背包重量,背包新的总价值取下面两者最大值:
//1,不取i物品的最大总价值;
//2,取了i物品,i物品的价值加上,在剩余容量为(j-weight(i))中的最大价值。
//v[i][j]=Math.max(v[i-1][j],value[i-1]+v[i-1][j-weight[i-1]]);
if(v[i-1][j]<value[i-1]+v[i-1][j-weight[i-1]])
{
v[i][j]=value[i-1]+v[i-1][j-weight[i-1]];//当进行交换时
path[i][j]++;//路径变为1
}
else {
v[i][j]=v[i-1][j];
}
}
}
}
for(int i=0;i<=n;i++) {
for(int j=0;j<=capacity;j++) {
System.out.print(v[i][j]+ " ");
}
System.out.println();
}
for(int i=0;i<=n;i++) {//输出路径矩阵
for(int j=0;j<=capacity;j++) {
System.out.print(path[i][j]+ " ");
}
System.out.println();
}
int i=n,j=capacity;
while(i>0&&j>0) {//利用路径矩阵输出选取的id,从后往前看
if(path[i][j]==1)
{
j=j-weight[i-1];//为1就看剩余容量。
System.out.println(i);
}
i--;
}
}
}
完全背包:
可以自己解决自己的问题
当选择拿i物品后,继续与value[i-1]+v[i][j-weight[i-1]]做比较而不是value[i-1]+v[i-1][j-weight[i-1]]
//需要改这个地方,其他一样
if(v[i-1][j]<value[i-1]+v[i][j-weight[i-1]])
{
v[i][j]=value[i-1]+v[i][j-weight[i-1]];//当进行交换时
path[i][j]++;//路径变为1
}