vs[i]=Math.max(v[j-1]+vs[i-j], vs[i]);为啥未出现的vs[i]（max里边的vs[i]）可以和自己比较

Question

package testOne;
//长度i   1 2 3  4   5   6   7   8   9  10 
//价格pi  1 5 8  16  10  17  17  20  24 30
//钢条切割问题是这样的：给定一段长度为L英寸的钢条和一个价格表pi(i=1,2,...n)
//求切割钢条方案，使得销售收益利润最大
//注意，如果长度为L英寸的钢条的价格pn足够大，最优解可能就是完全不需要切割。
public class Cut {
    static int[]l= {1,2,3,4,5,6,7,8,9,10};//长度
    static int[]v= {1,5,8,16,10,17,17,20,24,30};//价值
    static int L=10;// 总长度
    static int vs[]=new int[L+1];
    public static void main(String[] args) {
        System.out.println(dp());
        }
         static int dp() {
             vs[0]=0;
             for(int i=1;i<=L;i++) {//拥有刚条数
                 for(int j=1;j<=i;j++) {//保留j整数段
                     vs[i]=Math.max(v[j-1]+vs[i-j], vs[i]);//?????????为啥未出现的vs[i]可以和自己比较
                 }
             }
             return vs[L];
        }
    }

vs[i]=Math.max(v[j-1]+vs[i-j], vs[i]);为啥未出现的vs[i]（max里边的vs[i]）可以和自己比较

Answer 1

2301_79438322 晚上好🌙🌙🌙
本答案参考ChatGPT-3.5

未出现的vs[i]可以和自己比较的原因是，在这个特定的动态规划问题中，我们可以将切割的过程看作是将长度为i的钢条切割成两段，其中一段的长度为j，另一段的长度为i-j。我们在这个问题中考虑的是每种可能的切割方案，对于每次切割，我们比较两种情况：将长度为j的钢条继续切割或不切割。

解决方案如下：

1. 创建一个一维数组vs，长度为L+1，用来保存切割每段长度的最大价值。
2. 初始化vs[0]为0，表示长度为0的钢条的最大价值为0。
3. 然后从长度为1开始，逐步计算vs[i]的值。
4. 对于每个i，我们考虑每个切割点j，其中j的取值范围为1到i。
5. 对于每个切割点j，计算切割钢条的两段的最大价值v[j-1]+vs[i-j]。
6. 对于每个j，取这些最大价值中的最大值，并赋给vs[i]。
7. 最后vs[L]就是长度为L的钢条的最大价值。

修改后的代码如下：

public class Cut {
    static int[] l = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};   //长度
    static int[] v = {1, 5, 8, 16, 10, 17, 17, 20, 24, 30};   //价值
    static int L = 10;   // 总长度
    static int vs[] = new int[L + 1];

    public static void main(String[] args) {
        System.out.println(dp());
    }

    static int dp() {
        vs[0] = 0;
        for (int i = 1; i <= L; i++) {
            for (int j = 1; j <= i; j++) {
                vs[i] = Math.max(v[j - 1] + vs[i - j], vs[i]);
            }
        }
        return vs[L];
    }
}

在这段代码中，对于每个切割点j，我们将长度为j的钢条继续切割或者不切割的情况分别计算了其最大价值，并比较得到最大值。所以未出现的vs[i]（max里边的vs[i]）可以和自己比较。