背包问题

首先给你两个数组w和v表示货物的重量和价值

每种货物的数量1。

重量和价值都是大于等于0的。

还有一个参数int bag表示背包有多大。

返回在不超过背包容量的最大价值

想法：尝试！！-》动态

从左往右依次尝试

假设有三个货物

暴力枚举，最佳方案肯定在其中。要做的就是将这种想法，变成递归的版本。

/**
 * @Auther: oyy0v0
 * @Date: 2023/7/13 - 07 - 13 - 16:54
 * @Description: Test
 * @version: 1.0
 */
public class test {
    public static int knapsack(int[] w,int[] v,int bag){
        if(w.length!=v.length || w.length==0||v.length==0||bag<0){
            return 0;
        }
        //尝试函数
        return process(w,v,0,bag);
    }
    //返回最大价值
    public static int process(int[] w,int[] v, int index,int bag){
        if(bag<0){
            return -1;
        }
        //越界位置，表示没货了
        if(index==w.length){
            return 0;
        }
        //第一种情况，不要货物
        int p1 = process(w,v,index+1,bag);
        //第二种情况要货物
        int next = process(w,v,index+1,bag-w[index]);
        //表示货物超了
        int p2 = 0;
        if(next != -1){
            p2 = v[index] + next;
        }
        return Math.max(p1,p2);
    }
    //这是main方法，程序的入口
    public static void main(String[] args) {
        //背包问题给的三个参数
        int[] w = {1,2};
        int[] v = {3,4};
        int bag = 2;
        int result = knapsack(w,v,bag);
        System.out.println(result);

    }
}