算法分析

注意:用什么类型的转移方程只由第i个物品是什么类型决定

时间复杂度 $O(n^2)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    static int N = 1010;
    static int[] f = new int[N];
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = reader.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        for(int i = 1;i <= n;i++)
        {
            String[] s2 = reader.readLine().split(" ");
            int v = Integer.parseInt(s2[0]);
            int w = Integer.parseInt(s2[1]);
            int s = Integer.parseInt(s2[2]);
            if(s == 0)
            {
                for(int j = v;j <= m;j++)
                {
                    f[j] = Math.max(f[j], f[j - v] + w);
                }
            }
            else
            {
                if(s == -1) s = 1;
                for(int k = 1;k <= s;k *= 2)
                {
                    for(int j = m;j >= k * v;j--)
                    {
                        f[j] = Math.max(f[j], f[j - k * v] + k * w);
                    }
                    s -= k * v;
                }
                if(s > 0)
                {
                    for(int j = m;j >= s * v;j--)
                        f[j] = Math.max(f[j], f[j - s * v] + s * w);
                }
            }
        }
        System.out.println(f[m]);
    }
}