题目描述

多重背包问题

JAVA 代码 完整版

import java.util.*;
import java.io.*;

class Main{
    static int N = 12010, M = 2010;
    static int[] v = new int[N], w = new int[N];
    static int[] f = new int[M];

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        int cnt = 0;
        for(int i = 1; i<=n;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int s = sc.nextInt();

            int k = 1;
            while(k<=s){
                cnt ++;
                v[cnt] = a*k;
                w[cnt] = b*k;
                s-=k;//每次更新s = s-k的
                k*=2;//每次也更新 k = k*2

            }
            //如果s 余1的话.
            if(s>0){
                cnt ++;
                v[cnt] = a*s;
                w[cnt] = b*s;
            }

        }

        //前面构建 s[i]种情况 的v[] w[] 数据, 
        //后面把用01背包解决就行了. 
        n = cnt;
        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]);
    }

}

JAVA 代码

助于理解代码~ 打印数据. 删了舍不得.

import java.util.*;
import java.io.*;

class Main{
    static int N = 12010, M = 2010;
    static int[] v = new int[N], w = new int[N];
    static int[] f = new int[M];

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        int cnt = 0;
        for(int i = 1; i<=n;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int s = sc.nextInt();
            System.out.println("元数据：v["+ i+"] = " + a + "   w["+ i+"] = " + b + "    s["+ i+"] = " + s);
            int k = 1;
            while(k<=s){
                cnt ++;
                v[cnt] = a*k;
                w[cnt] = b*k;
                System.out.println("while循环内:v["+ cnt +"] = " + a*k + "   w["+cnt+"] = " + b*k);
                System.out.println("更新前：s = " + s + "    k = " + k);
                s-=k;//每次更新s = s-k的
                k*=2;//每次也更新 k = k*2
                System.out.println("更新后：s = " + s + "    k = " + k);
                System.out.println();
            }
            //
            System.out.println("while结束 s = " + s);
            if(s>0){
                cnt ++;
                v[cnt] = a*s;
                w[cnt] = b*s;

                System.out.println("if判断内: v["+ cnt +"] = " + a*s + "   w["+cnt+"] = " + b*s);
            }
            System.out.println("-----------------for循环进入下一层------------------------ ");

        }
        n = cnt;
        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]);
    }

}