image.png image.png
来源

以下是自己写的

import java.util.Scanner;
public class test{
    public static void main(String[] args){
        int totalPersons = 10;
        int[] value = {500, 200, 300, 350, 400};
        int[] persons = {5, 3, 4, 3, 5};
      //这里储存整个maxMatri，实际上只用到了前一行，所以和上面的代码相比浪费空间了。
        int[][] maxMatri = new int[value.length][totalPersons + 1];

        for(int i = persons[0]; i < totalPersons + 1; ++i){
                maxMatri[0][i] = value[0];
        }

        for(int i = 1; i < value.length; ++i){

            for( int j = 1; j < totalPersons + 1; ++j){
                maxMatri[i][j] =j - persons[i] >= 0 ?  Math.max(maxMatri[i - 1][j], maxMatri[i - 1][j - persons[i]] + value[i]) : maxMatri[i -1][j];
            }
        }
        
        System.out.println(maxMatri[maxMatri.length - 1][maxMatri[0].length - 1]);
    }

}

import java.util.Scanner;
public class test{
    /**
     * more concise
     */
    public static void main(String[] args){
        int totalPersons = 10;
        int[] value = {500, 200, 300, 350, 400};
        int[] persons = {5, 3, 4, 3, 5};
        int[] maxProfit = new int[totalPersons + 1];

        for(int i = 0; i < value.length; ++i){

            for( int j = totalPersons; j >= persons[i]; --j){
                if( i == 0){
                    maxProfit[j] = value[i];
                    continue;
                }
                maxProfit[j] = Math.max(maxProfit[j], maxProfit[j - persons[i]] + value[i]);
                if( i == value.length -1 && j == totalPersons)
                    break;
            }

        }
        
        System.out.println(maxProfit[totalPersons]);
    }

}

01背包

也可以这么解

import java.util.Scanner;
public class test{
    public static void main(String[] args){
        //weight
        int [] w = {2,2,6,5,4};
        //value
        int [] v = {6,3,5,4,6};
        System.out.println(package01(w, v, 10));
    }

    private static int package01(int w[], int v[], int totalW){
        /**
         * This method wastes memory
         */
        // int[] preF = new int[totalW + 1];
        // int[] f = new int[totalW + 1];
        // for(int i = 0; i < w.length; ++i){
        //     for(int j = 0; j < totalW + 1; ++j){
        //         if(j == 0){
        //             preF[j] = w[0];
        //             continue;
        //         }
        //         f[j] =  j - w[i] > 0? Math.max(preF[j], preF[j - w[i]] + v[i]) : preF[j];
        //     }
        //     for(int j = 1; j < totalW + 1; ++j){
        //         preF[j] = f[j];
        //     }
        // }
        int [] maxp = new int [totalW + 1];

        for(int i = 0; i < w.length; ++i){
            for(int j = totalW; j >= w[i]; --j){
                maxp[j] = Math.max(maxp[j], maxp[j - w[i]] + v[i]);
            }
        }

        return maxp[totalW];
    }

}

完全背包

只需修改为

        for(int i = 0; i < w.length; ++i){
            for(int j = w[i]; j < totalW+1; ++j){
                maxp[j] = Math.max(maxp[j], maxp[j - w[i]] + v[i]);
            }
        }

多重背包

题目：输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。

定理：一个正整数n可以被分解成1,2,4,…,2^(k-1),n-2k+1（k是满足n-2^{k+1>0的最大整数）的形式，且1～n之内的所有整数均可以唯一表示成1,2,4,…,2}(k-1),n-2^k+1中某几个数的和的形式.
证明如下：

（1） 数列1,2,4,…,2^(k-1),n-2k+1中所有元素的和为n，所以若干元素的和的范围为：[1, n]；
（2）如果正整数t<= 2^k – 1,则t一定能用1,2,4,…,2^{(k-1)中某几个数的和表示，这个很容易证明：我们把t的二进制表示写出来，很明显，t可以表示成n=a0*2}0+a12^1+…+ak2^（k-1），其中ak=0或者1，表示t的第ak位二进制数为0或者1.
（3）如果t>=2^k,设s=n-2k+1，则t-s<=2^{k-1，因而t-s可以表示成1,2,4,…,2}(k-1)中某几个数的和的形式，进而t可以表示成1,2,4,…,2^(k-1)，s中某几个数的和（加数中一定含有s）的形式。
（证毕！）

import java.util.ArrayList;
import java.util.Scanner;
public class test{
    /**
     * more concise
     */
    public static void main(String[] args){
        int money = 8;
        int[] value = {2,4};
        int[] weight = {100, 100};
        int[] amount = {4, 2};
        
        System.out.println(multiplePackage(money, value, weight, amount));
    }

    private static int multiplePackage(int money, int[] value, int[] weight, int[] amount){
        int[] dp = new int[money + 1];

        //关键
        ArrayList<Integer> valueList = new ArrayList<>();
        ArrayList<Integer> weightList = new ArrayList<>();
        for(int i = 0; i < value.length; ++i){
            for(int j = 1; j < amount[i]; j <<= 1){
                valueList.add(value[i] * j);
                weightList.add(weight[i] * j);
                amount[i] -= j;
            }
            if(amount[i] > 0){
                valueList.add(amount[i] * value[i]);
                weightList.add(amount[i] * weight[i]);
            }
        }

      //还是01背包的解法
        for(int i = 0; i < valueList.size(); ++i){
            for(int j = money; j >= valueList.get(i); --j){
                if( dp[j] < dp[j - valueList.get(i)] + weightList.get(i)){
                        dp[j] = dp[j - valueList.get(i)] + weightList.get(i);
                }
            }
        }

        return dp[money];
    }

}

参考