01背包

问题描述

有n件物品，每件物品的重量为w[i]，价值为c[i]。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的价值最大。其中每种物品都有1件。

样例输入

5 8 // n == 5, V == 8

3 5 1 2 2 //w[i] 重量

4 5 2 1 3 //c[i] 价值

结果为 10

模版

package 背包问题;

import java.util.Scanner;

public class 零一背包 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int V = in.nextInt();
        int[] w = new int[n];
        int[] c = new int[n];
        int[] dp = new int[V+1];
        //输入一组物品的重量
        for(int i = 0; i < n; i++){
            w[i] = in.nextInt();
        }
        //输入一组物品的价值
        for(int i = 0; i < n; i++){
            c[i] = in.nextInt();
        }
        int maxn = 0;
        //核心过程
        for(int i = 0; i < n; i++){
            for(int v = V; v >= w[i]; v--){
                dp[v] = Math.max(dp[v],dp[v - w[i]] + c[i]);
                maxn = Math.max(dp[v],maxn);
            }
        }
        System.out.println(maxn);
    }
}