算法-动态规划-背包问题-附一

发布于:2023-01-04 ⋅ 阅读:(382) ⋅ 点赞:(0)

背包问题基础: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个物品的体积和价值。

1 \le n,V,v_i,w_i \le 10001\leq n

输出描述:

输出有两行,第一行输出第一问的答案,第二行输出第二问的答案,如果无解请输出0。

输入

3 5
2 10
4 5
1 4

输出

14

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种物品的体积和价值。

1 \le n, V \le 10001\leqslant n, V\leq 1000

输出描述:

输出有两行,第一行输出第一问的答案,第二行输出第二问的答案,如果无解请输出0。

输入 

2 6
5 10
3 1

输出 

10

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)不继续分割的情况,此时自己就是最大

 


网站公告

今日签到

点亮在社区的每一天
去签到