背包问题基础：Java-算法-动态规划-背包问题?
一. 背包问题介绍
????????见Java-算法-动态规划-背包问题
二. 0/1背包
????????见Java-算法-动态规划-背包问题
三.完全背包
????????见Java-算法-动态规划-背包问题
四. 多重背包
????????见Java-算法-动态规划-背包问题
五. leetcode&牛客实战（附）
1. NC AB40?【模板】01背包
描述
你有一个背包，最多能容纳的体积是V。
现在有n个物品，第i个物品的体积为v_ivi??,价值为w_iwi?。
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
输入描述：
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数v_ivi?和w_iwi?，表示第i个物品的体积和价值。
输出描述：
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。
输入
3 5
2 10
4 5
1 4
输出
14
9?
import java.util.*;
import java.io.*;
public class Main{
public static void main(String args[]) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
String[] strnum = str.split(" ");
int line = Integer.parseInt(strnum[0]);
int cap = Integer.parseInt(strnum[1]);
int[][] nums = new int[line][2];
String str1 = "";
int index = 0;
while((str1 = br.readLine()) != null){
String[] st = str1.split(" ");
int v = Integer.parseInt(st[0]);
int w = Integer.parseInt(st[1]);
nums[index][0] = v;
nums[index][1] = w;
index++;
}
// for(int i = 0; i < nums.length; i++){
// for(int j = 0; j < nums[0].length; j++){
// System.out.print(nums[i][j]+" ");
// }
// System.out.println();
// }
int[] dp = new int[cap+1];
for(int i = 0; i < line; i++){
for(int j = cap; j >= nums[i][0]; j--){
dp[j] = Math.max(dp[j],dp[j-nums[i][0]]+nums[i][1]);
}
}
System.out.println(dp[cap]);
int[] dp_1 = new int[cap+1];
Arrays.fill(dp_1,Integer.MIN_VALUE);
dp_1[0] = 0;
for(int i = 0; i < line; i++){
for(int j = cap; j >= nums[i][0]; j--){
dp_1[j] = Math.max(dp_1[j],dp_1[j-nums[i][0]]+nums[i][1]);
}
}
if(dp_1[cap] < 0) dp_1[cap] = 0;
System.out.println(dp_1[cap]);
}
}2. NC AB41?【模板】完全背包?
描述
你有一个背包，最多能容纳的体积是V。
现在有n种物品，每种物品有任意多个，第i种物品的体积为v_ivi??,价值为w_iwi?。
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
输入描述：
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数v_ivi?和w_iwi?，表示第i种物品的体积和价值。
输出描述：
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。
输入?
2 6
5 10
3 1
输出?
10
2?
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String info = br.readLine();
String[] infoarr = info.split(" ");
int num = Integer.parseInt(infoarr[0]);
int cap = Integer.parseInt(infoarr[1]);
int[] nums = new int[num];
int[] weight = new int[num];
for(int i = 0; i < num; i++){
String info1 = br.readLine();
String[] infoarr1 = info1.split(" ");
nums[i] = Integer.parseInt(infoarr1[0]);
weight[i] = Integer.parseInt(infoarr1[1]);
}
int[] dp = new int[cap+1];
for(int i = 0; i < num; i++){
for(int j = nums[i]; j <= cap; j++){
dp[j] = Math.max(dp[j],dp[j-nums[i]]+weight[i]);
}
}
System.out.println(dp[cap]);
int[] dp2 = new int[cap+1];
Arrays.fill(dp2,Integer.MIN_VALUE);
dp2[0] = 0;
for(int i = 0; i < num; i++){
for(int j = nums[i]; j <= cap; j++){
dp2[j] = Math.max(dp2[j],dp2[j-nums[i]]+weight[i]);
}
}
if(dp2[cap] < 0) {
System.out.println(0);
}
else{
System.out.println(dp2[cap]);
}
}
}3. AB39?[NOIP2001]装箱问题
描述
有一个箱子容量为V（正整数，0 ≤ V ≤ 20000），同时有n个物品（0＜n ≤ 30），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入描述：
1个整数，表示箱子容量
1个整数，表示有n个物品
接下来n行，分别表示这n个物品的各自体积
输出描述：
1个整数，表示箱子剩余空间。
输入
24
6
8
3
12
7
9
7
输出?
0
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String capstr = br.readLine();
int cap =Integer.parseInt(capstr);
capstr = br.readLine();
int num =Integer.parseInt(capstr);
int[] nums = new int[31];
int index = 0;
String str = "";
while( (str = br.readLine()) != null){
nums[index++] = Integer.parseInt(str);
}
int[] dp = new int[cap+1];
for(int i = 0; i < num; i++){
for(int j = cap; j >=nums[i]; j--){
dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
}
}
System.out.println(cap-dp[cap]);
}
}本题小结：（1）只能用一次，01背包
? ? ? ? ? ? ? ? ? （2）dp滚动，且01，用到上一层信息，所以，从后往前
4. leetcode343 整数拆分
????????给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。返回你可以获得的最大乘积 。
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
错误：
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i <= n; i++){
for(int j = 1; j <= i; j++){
dp[i] = Math.max(dp[i],dp[i-j]*j);
}
}
return dp[n];
}
}
?错误原因：j*(i-j)不继续分割，此时自己就是最大
?正确版本：
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i <= n; i++){
for(int j = 1; j <= i; j++){
dp[i] = Math.max(dp[i],Math.max(j*(i-j),dp[i-j]*j));
}
}
return dp[n];
}
}本题小结：（1）可重复取数，即完全背包
??????????????????（2）每层比较j*(i-j)不继续分割的情况，此时自己就是最大
?