背包问题整理

1.01背包

题目描述
小明有一个容量为 V 的背包。

这天他去商场购物，商场一共有N 件物品，第 i 件物品的体积为 wi，价值为 vi。

小明想知道在购买的物品总体积不超过 V的情况下所能获得的最大价值为多少，请你帮他算算。

输入描述
输入第 11 行包含两个正整数 N,V，表示商场物品的数量和小明的背包容量。

第 2∼N+1 行包含 2 个正整数 w,v，表示物品的体积和价值。

1≤N≤100 ,1≤V≤1000,≤wi,vi≤10000。

输出描述
输出一行整数表示小明所能获得的最大价值。

样例

输入

5 20
1 6
2 5
3 8
5 15
3 3 

输出

37

代码示例

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int n = scan.nextInt();int m = scan.nextInt();int[] w = new int[m+1];int[] v = new int[n+1];for(int i = 1;i<=n;i++){v[i] = scan.nextInt();w[i] = scan.nextInt();}int[][] dp = new int[n+1][m+1];for(int i = 1;i<=n;i++){for(int j = 1;j<=m;j++){if(j>=v[i]){dp[i][j] = Math.max(dp[i][j-v[i]]+w[i],dp[i-1][j]);}else{dp[i][j] = dp[i-1][j];}}}System.out.println(dp[n][m]);scan.close();}
}

2.完全背包

问题描述

有 N 件物品和一个体积为 M 的背包。第 ii 个物品的体积为 vi​，价值为 wi​。每件物品可以使用无限次。

请问可以通过什么样的方式选择物品，使得物品总体积不超过 M 的情况下总价值最大，输出这个最大价值即可。

输入格式

第一行输入两个正整数 N,M。(1≤N,M≤1000)(1≤N,M≤1000)

接下来 NN 行，每行输入两个整数 vi,wi​。(0≤vi,wi≤1000)(0≤vi​,wi​≤1000)

输出格式

输出一个整数，表示符合题目要求的最大价值。

样例输入

4 5
1 2
2 4
3 4
4 5

样例输出

10

说明

你可以选择 1 个第一个物品和 2 个第二个物品。

代码示例

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // 物品数量int m = sc.nextInt(); // 背包容量int[] w = new int[n]; // 物品体积数组int[] v = new int[n]; // 物品价值数组// 输入每种物品的体积和价值for (int i = 0; i < n; i++) {w[i] = sc.nextInt();v[i] = sc.nextInt();}// 创建一个一维数组dp，dp[i]表示背包容量为i时的最大价值int[] dp = new int[m + 1];// 动态规划求解for (int i = 0; i < n; i++) {for (int j = w[i]; j <= m; j++) {dp[j] = Math.max(dp[j - w[i]] + v[i], dp[j]);}}// 输出最大价值System.out.println(dp[m]);}
}