题目描述

blablabla

JAVA代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    /**
     * 1.为什么不能用完全背包问题的思路去解决
     * 因为完全背包没有物品个数限制，所以只要体积够用就可以一直选，没有最后一项。
     * 完全背包最后那一项体积是刚好用完了的，而多重背包最后那一项之后还有体积没用完，所以多重背包的式子后面还可以多减一项，而完全背包就不行了。
     * 2.优化方法及代码
     *
     *
     * 3.01背包问题的优化写法
     * https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html#%E4%B8%80%E7%BB%B4dp%E6%95%B0%E7%BB%84-%E6%BB%9A%E5%8A%A8%E6%95%B0%E7%BB%84
     * @param args
     */
    static int N = 12010;
    static int M = 2010;
    static int v[] = new int[N];
    static int w[] = new int[N];//
    static int f[] = new int[M];//体积小于M
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1[] = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);//物品种数
        int m = Integer.parseInt(s1[1]);//背包容积。
        int cnt = 0;//分组的组别
        for (int i = 1; i <= n; i++) {
            String ss[] = br.readLine().split(" ");
            int a = Integer.parseInt(ss[0]);
            int b = Integer.parseInt(ss[1]);
            int s = Integer.parseInt(ss[2]);
            int k = 1;//组别里面的个数
            /**
             * 第一个组1
             * 第二个组2
             * 第三个组4
             * 第四个组8
             * ...
             */
            while (k <= s){
                cnt++;//组别数先增加
                v[cnt] = a*k;//这个组的整体体积
                w[cnt] = b*k;//这个组的整体价值
                s -= k;//s减小
                k *= 2;//组别数成倍增加
            }
            //剩余的最后一组
            if(s>0){
                cnt++;
                v[cnt] = a*s;
                w[cnt] = b*s;
            }
        }

        n = cnt;//我们每次要枚举的是组数
        //优化后的01背包
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= v[i]; j--) {
                f[j] = Math.max(f[j],f[j-v[i]]+w[i]);
            }
        }
        System.out.println(f[m]);
    }
}