Knapsack Problem

update Feb 16 2019, 13:49

这里有一个讲解背包问题的视频，感觉不错：https://www.youtube.com/watch?v=nleY0-eexps .

01背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式:

输出一个整数，表示最大价值。

数据范围
    0<N,V≤1000
    0<vi,wi≤1000
输入样例
    4 5
    1 2
    2 4
    3 4
    4 5
输出样例：
    8

Basic Idea:

• Java Code:

    import java.util.Scanner;
  
    public class Solution {
        public static int solve(int[] weights, int[] values, int V) {
            int[][] dp = new int[weights.length + 1][V + 1];
            for (int i = 1; i < dp.length; ++i) {
                for (int j = 0; j <= V; ++j) {
                    if (j - weights[i - 1] >= 0) {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
            int res = 0;
            for (int i = 0; i <=V; ++i) res = Math.max(res, dp[weights.length][i]);
            return res;
        }
  
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt(), V = sc.nextInt();
            int[] weights = new int[N], values = new int[N];
            for (int i = 0; i < N; ++i) {
                weights[i] = sc.nextInt();
                values[i] = sc.nextInt();
            }
            sc.close();
  
            System.out.println(solve(weights, values, V));
        }
    }