01 背包问题

[编程题]0/1 背包问题

热度指数：3521 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

有为N件物品，它们的重量w分别是w1,w2,...,wn，它们的价值v分别是v1,v2,...,vn，每件物品数量有且仅有一个，现在给你个承重为M的背包，求背包里装入的物品具有的价值最大总和？

输入描述:

物品数量N=5件
重量w分别是2 2 6 5 4
价值v分别是6 3 5 4 6
背包承重为M=10

输出描述:

背包内物品最大总和为15

示例1

输入

输出

算法知识视频讲解

Java

湮灭丶星空

经典01背包模板题(JAVA实现)

使用动态规划


import java.util.Scanner;
 public class Main {
    static int w[];
    static int v[];
    static int dp[];
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int N=scanner.nextInt();
        w=new int[N];
        v=new int[N];
        int C=scanner.nextInt();
        dp=new int[C+1];
        for (int i = 0; i < N; i++) {
            w[i]=scanner.nextInt();
        }
        for (int i = 0; i < N; i++) {
            v[i]=scanner.nextInt();
        }
        for (int i = 0; i < N; i++) {   //物品
            for (int j = C; j >=w[i]; j--) {   //容量
                dp[j]=Math.max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        System.out.println(dp[C]);
    }
}

使用递归+记忆化数组

import java.util.Scanner;

public class Main {
    static int N;
    static int W;
    static int w[];
    static int v[];
    static int a[][];
    static int dfs(int index,int C){  //C 表示当前容量
        if(index>N)return 0;
        if(C<0)return 0;
        if(a[index][C]!=0)return a[index][C];
        if(C-w[index]<0) {

            a[index][C]= dfs(index + 1, C);
        }else {
            a[index][C]= Math.max(v[index] + dfs(index + 1, C - w[index]), dfs(index + 1, C));
        }
        return a[index][C];
    }
    public static void main(String[] args) {
        Scanner reader=new Scanner(System.in);
        N= reader.nextInt();
        W= reader.nextInt();
        w=new int[N+1];
        v=new int[N+1];
        a=new int[N+1][W+1];
        for (int i = 0; i < N; i++) {
            w[i]= reader.nextInt();
        }
        for (int i = 0; i < N; i++) {
            v[i]= reader.nextInt();
        }
        System.out.println(dfs(0,W));
    }

}

发表于 2021-04-20 23:42:23 回复(0)