试题算法提高 01背包

朴灿烈づ我的快乐病毒、 2022-11-13 06:23 125阅读 0赞

问题描述  
　　给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.  
输入格式  
　　输入的第一行包含两个整数n, m，分别表示物品的个数和背包能装重量。  
　　以后N行每行两个数Wi和Vi,表示物品的重量和价值  
输出格式  
　　输出1行，包含一个整数，表示最大价值。  
样例输入  
3 5  
2 3  
3 5  
4 7  
样例输出  
8  
数据规模和约定  
　　1<=N<=200,M<=5000.

import java.io.BufferedInputStream;
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Scanner;
    public class Main{ 
        public static void main(String args[]){ 
            Scanner in=new Scanner(new BufferedInputStream(System.in));
            int n=in.nextInt(),m=in.nextInt();
            int[] w=new int[n],value=new int[n],res=new int[m+1];
            for(int i=0;i<n;i++) { 
            	w[i]=in.nextInt();
            	value[i]=in.nextInt();
            }
            for(int i=0;i<n;i++) { 
            	for(int j=m;j>=w[i];j--) { 
            		res[j]=Math.max(res[j], res[j-w[i]]+value[i]);
            	}
            }
            System.out.println(res[m]);
        }
    }

解析：

for(int i=0;i<n;i++) { 
        for(int j=m;j>=w[i];j--) { 
            res[j]=Math.max(res[j], res[j-w[i]]+value[i]);
        }
    }

第一个for循环遍历每个物品  
第二个for循环，空间里放与不放间取最大值，因为遍历是向下的，之前只对\[0,i-1\]这个区间的物品进行处理，不会存在重复放置相同的物品

发表评论取消回复

表情：

评论列表（有 0 条评论，125人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法|动态规划No.31 | 01背包问题】01背包模板题

【算法|动态规划No.31 | 01背包问题】01背包模板题

￡神魔★判官ぃ/ 2024年04月27日 06:49/ 0 赞/ 69 阅读

相关回溯算法--01背包问题

目录回溯算法--01背包问题 \[算法描述\] \[回溯法基本思想\] 法一：法二：代码：运行结果代码改进 -----------------

朴灿烈づ我的快乐病毒、/ 2024年03月24日 15:14/ 0 赞/ 55 阅读

相关 01背包

01背包题目描述给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个输入的第一行包

爱被打了一巴掌/ 2022年12月04日 04:27/ 0 赞/ 163 阅读

相关试题算法提高 01背包

问题描述　　给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个. 输入格式　　输入的第一行包含

朴灿烈づ我的快乐病毒、/ 2022年11月13日 06:23/ 0 赞/ 126 阅读

相关【C语言/算法之 01 背包】完全背包

\[题目\] 有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。第i种物品的费用是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使这些物品的费用总

古城微笑少年丶/ 2022年08月05日 04:19/ 0 赞/ 170 阅读

相关 01背包,完全背包

01背包问题：一个背包总容量为V，现在有N个物品，第i个物品体积为weight\[i\]，价值为value\[i\]，现在往背包里面装东西，怎么装能使背包的内物品价值最大？

男娘i/ 2022年06月09日 04:16/ 0 赞/ 230 阅读

相关 01背包

> 题目：有一个背包，体积为m，现在给你n个石头，每个石头都有价值和体积，问这个背包可以装下多大价值的石头。 > > 输入： > 第一行两个整数n，m，分别代表石头的个数

╰半夏微凉°/ 2022年06月08日 09:37/ 0 赞/ 191 阅读

相关算法——背包问题 01背包+完全背包+多重背包

01背包：https://biancheng.love/problem/51/index 有n 种不同的物品，每个物品有两个属性，weight重量，value 价值，现在给一

ゞ浴缸里的玫瑰/ 2022年06月06日 10:41/ 0 赞/ 294 阅读

相关 01背包

01背包 > 且说上一周的故事里，小Hi和小Ho费劲心思终于拿到了茫茫多的奖券！而现在，终于到了小Ho领取奖励的时刻了！ > > 小Ho现在手上有M张奖券，而奖品区有N

水深无声/ 2022年05月31日 06:29/ 0 赞/ 597 阅读

相关背包问题—01背包、完全背包

01背包问题题目有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。思路这

末蓝、/ 2022年05月30日 10:10/ 0 赞/ 346 阅读