IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 算法-动态规划-背包问题-附一 -> 正文阅读

[数据结构与算法]算法-动态规划-背包问题-附一

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

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

输出描述:

输出有两行,第一行输出第一问的答案,第二行输出第二问的答案,如果无解请输出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)不继续分割的情况,此时自己就是最大

?

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-09-04 01:36:44  更:2022-09-04 01:38:22 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/28 17:36:43-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计