方法1：记忆化搜索

/**
 * 方法1  记忆化搜索 递归dp  f(i,j)=max(f(i-1,j),f(i-1,j-v)+w,f(i-1,j-v*2)+w*2,....f(i-1,j-v*s)+s*w)
 * 
 **/
 import java.util.*;
 public class Main{
     static int[][] f=new int[102][102];
     static int n;
     static int V;
     static int[][] arr;
     public static void main(String [] args){
         Scanner sc=new Scanner(System.in);
         n=sc.nextInt();
         V=sc.nextInt();
         arr=new int[n+1][3];
         for(int i=1;i<=n;i++){
             for(int j=1;j<=V;j++){
                 f[i][j]=-1;
             }
         }
         for(int i=1;i<=n;i++){
                 int v=sc.nextInt();
                 int w=sc.nextInt();
                 int s=sc.nextInt();
                 arr[i]=new int[]{v,w,s};
         }
         System.out.println(dp(n,V));
    }
     public static int dp(int i,int j){
         if(f[i][j]!=-1) return f[i][j];
         int v=arr[i][0],w=arr[i][1],s=arr[i][2];
         int t=0;
         for(;t<=s&&j-t*v>=0;t++){
             f[i][j]=Math.max(f[i][j],dp(i-1,j-t*v)+t*w);   
         }
         return f[i][j];
     }
 }

算法2 二进制优化

/**
 * 方法2：转01背包
 * 0-s  可以用几个数的组合表示，那么就可以把这几个数当做0-1背包
 * 先用2进制去试，最后不足直接剩下。例如 8可以用：1,2,4,1
*/
import java.util.*;
public class Main{
    public static void main(String [] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int V=sc.nextInt();
        int [][] bao=new int[6000][2];
        int count=0;
        int[] f=new int[V+1];
        for(int i=0;i<n;i++){
            int v=sc.nextInt();
            int w=sc.nextInt();
            int s=sc.nextInt();
            for(int t=1;t<=s;t=t*2){
                s=s-t;//这个最开始放在了for里面了，结果一直错。。尴尬  
                bao[++count]=new int[]{v*t,w*t};
            }
            if(s!=0) bao[++count]=new int[]{v*s,w*s};
        }
        for(int i=1;i<=count;i++){
            for(int j=V;j>=bao[i][0];j--){
                // System.out.println(i+" "+j);
                f[j]=Math.max(f[j],f[j-bao[i][0]]+bao[i][1]);
            }
        }
        System.out.println(f[V]);
    }
}

方法3：正常做法。

//正常做法
import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int V=sc.nextInt();
        int []f=new int[V+1];
        for(int i=1;i<=n;i++){
            int v=sc.nextInt();
            int w=sc.nextInt();
            int s=sc.nextInt();
            for(int j=V;j>=v;j--){
                for(int k=0;k<=s&&j-k*v>=0;k++){
                    f[j]=Math.max(f[j],f[j-k*v]+k*w);
                }
            }
        }
        System.out.println(f[V]);
    }
}