题目：题目链接

image.png

  1. import java.util.Scanner;
  2. import java.util.ArrayList;
  3. public class Main{
  4.     public static void main(String[] args){
  5.         Scanner sc=new Scanner(System.in);
  6.         int N=sc.nextInt();
  7.         int V=sc.nextInt();
  8.         ArrayList<int[]> al=new ArrayList<>();
  9.         for(int i=0;i<N;i++){
  10.             int v=sc.nextInt();
  11.             int w=sc.nextInt();
  12.             int s=sc.nextInt();
  13.             if(s==-1){
  14.                 al.add(new int[]{-1,v,w});
  15.             }
  16.             if(s==0){
  17.                 al.add(new int[]{0,v,w});
  18.             }
  19.             if(s>0){
  20.                 for(int k=1;k<=s;k++){
  21.                     s=s-k;
  22.                     al.add(new int[]{-1,k*v,k*w});
  23.                 }
  24.                 if(s!=0){
  25.                     al.add(new int[]{-1,s*v,s*w});
  26.                 }   
  27.             }
  28.         }
  29.         int[] dp=new int[V+1];
  30.         for(int i=0;i<al.size();i++){
  31.             if(al.get(i)[0]==-1){
  32.                 for(int j=V;j>=al.get(i)[1];j--){
  33.                     dp[j]=Math.max(dp[j],dp[j-al.get(i)[1]]+al.get(i)[2]);
  34.                 }
  35.             }
  36.             if(al.get(i)[0]==0){
  37.                 for(int j=al.get(i)[1];j<=V;j++){
  38.                     dp[j]=Math.max(dp[j],dp[j-al.get(i)[1]]+al.get(i)[2]);
  39.                 }
  40.             }
  41.         }
  42.         System.out.println(dp[V]);
  43.     }
  44. }

就是把多重背包 问题优化转到01背包问题，然后每个状态的转化要根据条件来做选择，也就是说不是一个dp方程了，但是对于某个物品 时候是同一个。根据到选 某个物品，状态选择（或者叫做dp方程）发生改变。