背包九讲之第三讲多重背包问题

1.最简单的解法多重背包问题。题目链接（注意下面的所有题只是数据范围不一样而已，也就是卡时间是不一样的。）

多重背包问题和01背包问题是一样的，只有一个地方有区别就是dp函数，01背包就两种情况，要还是不要也就是0个或者1个。而多重背包是最多有s个，也就是0,1,2，、、s。
多重背包问题只需要改dp函数即可。
dp[i][j]=Max{dp[i-1][j],dp[j-1][j-v]+w,dp[i][j-2v]+2w…….}
我的代码比y总大大还要优化了一点哦。

import java.util.Scanner;
public class Main{
    public static void main(String[]  args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int V=sc.nextInt();
        int[] dp=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=1;k<=s&&k*v<=j;k++){
                    dp[j]=Math.max(dp[j],dp[j-k*v]+k*w);
                }    
            }
        }
        System.out.println(dp[V]);
    }
}

2.第一种优化，转化为01背包。多重背包的二进制优化方法。题目链接

因为7 最少可以由1,2,4 自由组合0-7.
8可以由 1,2,4,1
也就是说，从1,2,4，。。看什么时候下一个数字比剩余还要大就不行了，如果小就继续可以。
也就是说以后如果遇到这种想表达一个数的范围例如0-10 最少可以用1,2,4,3 来表达（每一个只用一次哈）
但是不是说均匀概率哈。

import java.util.Scanner;
import java.util.ArrayList;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int V=sc.nextInt();
        ArrayList<int[]> al=new ArrayList<>();
        for(int i=0;i<N;i++){
            int v=sc.nextInt();
            int w=sc.nextInt();
            int s=sc.nextInt();
            for(int k=1;k<=s;k=k*2){
                //下面这句话是精髓
                s=s-k;
                al.add(new int[]{v*k,w*k});
            }
            if(s!=0){
                al.add(new int[]{v*s,w*s});
            }
        }
        int[] dp=new int[V+1];
        for(int i=0;i<al.size();i++){
            for(int v=V;v>=al.get(i)[0];v--){
                dp[v]=Math.max(dp[v],dp[v-al.get(i)[0]]+al.get(i)[1]);
            }
        }
        System.out.println(dp[V]);
    }
}

3.最后的就是楼教主提出的男人八题中的思想，我还理解不了。。。。题目链接