java 动态规划（背包问题）

「爱情、让人受尽委屈。」 2022-11-21 11:23 216阅读 0赞

--------------------

### java 动态规划（背包问题） ###

### \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* ###

**背包问题**

**问题描述**

给定n个物体, 重量为：w1、w2、... wn, 价值：v1、v2、... vn, 
    背包承重：weight，如何放置物体使得在不超过weight的前提下总价值最大

**0-1背包：每个物体最多选择一次**

f(i,j)：总承重j、最多可选i个物品时，背包放置物品的最大价值
    
    wi <= j ==> 放置wi：f(i-1,j-wi)+vi、不放置wi：f(i-1,j)，取两者中较大者
    f(i,j)=max(f(i-1,j), f(i-1,j-wi)+vi)
    
    wi > j  ==> 不放置wi
    f(i,j)=f(i-1,j)

**有限背包：第i个物品的数量为ni**

f(i,j)：总承重j、最多可选i个物品时，背包放置物品的最大价值
    
    总承重为j时，物品wi可放置的最大数量：j/wi
    f(i,j)=max(f(i-1,j-kwi)+kv1), 0=< k <=j/wi 且k<=ni

**无限背包：物品的数量不限**

f(i,j)：总承重j、最多可选i个物品时，背包放置物品的最大价值
    
    总承重为j时，物品wi可放置的最大数量：j/wi
    f(i,j)=max(f(i-1,j-kwi)+kvi), 0=< k <=j/wi

### \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* ###

**示例**

**0-1背包**

![20201102203438301.png][]

**有限背包**

![20201102210724883.png][]

**无限背包：物品重量、物品价值同上，数量没有限制**

public class MyTest5 {
    
        public static int fun(int[] weight, int[] value, int total){
            if (weight.length==0||value.length==0){
                return -1;
            }
    
            if (total==0){
                return 0;
            }
    
            int length=weight.length;
            int[][] maxValue=new int[length][total+1];
    
            for (int j=1;j<=total;j++){
                for (int i=0;i<length;i++){
                    if (i==0){
                        if (weight[i]>j){
                            maxValue[i][j]=0;
                        }else {
                            maxValue[i][j]=value[i];
                        }
    
                        continue;
                    }
    
                    if (weight[i]>j){
                        maxValue[i][j]=maxValue[i-1][j];
                    }else {
                        maxValue[i][j]=Math.max(maxValue[i-1][j],maxValue[i-1][j-weight[i]]+value[i]);
                    }
                }
            }
    
            int max=0;
            for (int i=0;i<length;i++){
                if (max<maxValue[i][total]){
                    max=maxValue[i][total];
                }
            }
    
            return max;
        }
    
        public static int fun2(int[] weight, int[] value, int[] num, int total){
            if (total==0){
                return 0;
            }
    
            if (weight.length==0||value.length==0||num.length==0){
                return -1;
            }
    
            int length=weight.length;
            int[][] maxValue=new int[length][total+1];
    
            for (int j=1;j<=total;j++){
                for (int i=0;i<length;i++){
                    int n=Math.min(j/weight[i],num[i]);
    
                    if (i==0){
                        for (int k=0;k<=n;k++){
                            if (k*weight[i]<=j){
                                maxValue[i][j]=k*value[i];
                            }
                        }
    
                        continue;
                    }
    
                    for (int k=0;k<=n;k++){
                        if (k*weight[i]<=j){
                            maxValue[i][j]=Math.max(maxValue[i-1][j-k*weight[i]]+k*value[i],maxValue[i][j]);
                        }
                    }
                }
            }
    
            int max=0;
            for (int i=0;i<length;i++){
                if (max<maxValue[i][total]){
                    max=maxValue[i][total];
                }
            }
    
            return max;
        }
    
        public static int fun3(int[] weight, int[] value, int total){
            if (total==0){
                return 0;
            }
    
            if (weight.length==0||value.length==0){
                return -1;
            }
    
            int length=weight.length;
            int[][] maxValue=new int[length][total+1];
    
            for (int j=1;j<=total;j++){
                for (int i=0;i<length;i++){
                    int n=j/weight[i];
    
                    if (i==0){
                        for (int k=0;k<=n;k++){
                            maxValue[i][j]=k*value[i];
                        }
    
                        continue;
                    }
    
                    for (int k=0;k<=n;k++){
                        maxValue[i][j]=Math.max(maxValue[i-1][j-k*weight[i]]+k*value[i],maxValue[i][j]);
                    }
                }
            }
    
            int max=0;
            for (int i=0;i<length;i++){
                if (max<maxValue[i][total]){
                    max=maxValue[i][total];
                }
            }
    
            return max;
        }
    
        public static void main(String[] args){
            int[] weight={3,5,6,10};
            int[] value={20,50,30,20};
            int[] num={1,2,3,4};
            int total=20;
    
            System.out.println("0-1背包总价值最大为："+fun(weight,value,total));
            System.out.println("有限背包总价值最大为："+fun2(weight,value,num,total));
            System.out.println("无限背包总价值最大为："+fun3(weight,value,total));
        }
    }

**控制台输出**

0-1背包总价值最大为：100
    有限背包总价值最大为：150
    无限背包总价值最大为：200

[20201102203438301.png]: /images/20221120/7c9e7458632844a4b48ae61c18cee923.png
[20201102210724883.png]: /images/20221120/13ba6e988437414381f4f5351531ef5b.png