建网站用什么服务器,网件路由器恢复出厂设置,wordpress游戏网站模板,室内设计公司排名前100题目描述 你是一名宇航员#xff0c;即将前往一个遥远的行星。在这个行星上#xff0c;有许多不同类型的矿石资源#xff0c;每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球#xff0c;但你的宇航舱有一定的容量限制。 给定一个宇航舱#xff0c;最大容量为… 题目描述 你是一名宇航员即将前往一个遥远的行星。在这个行星上有许多不同类型的矿石资源每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球但你的宇航舱有一定的容量限制。 给定一个宇航舱最大容量为 C。现在有 N 种不同类型的矿石每种矿石有一个重量 w[i]一个价值 v[i]以及最多 k[i] 个可用。不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下最大化你所能获取的总价值。 输入描述 输入共包括四行第一行包含两个整数 C 和 N分别表示宇航舱的容量和矿石的种类数量。 接下来的三行每行包含 N 个正整数。具体如下 第二行包含 N 个整数表示 N 种矿石的重量。 第三行包含 N 个整数表示 N 种矿石的价格。 第四行包含 N 个整数表示 N 种矿石的可用数量上限。 输出描述 输出一个整数代表获取的最大价值。 多重背包
import java.util.*;
class Main{public static void main(String [] args) {Scanner sc new Scanner(System.in);/*** bagWeight:背包容量* n:物品种类*/int bagWeight, n;//获取用户输入数据中间用空格隔开回车键换行bagWeight sc.nextInt();n sc.nextInt();int[] weight new int[n];int[] value new int[n];int[] nums new int[n];for (int i 0; i n; i) weight[i] sc.nextInt();for (int i 0; i n; i) value[i] sc.nextInt();for (int i 0; i n; i) nums[i] sc.nextInt();int[] dp new int[bagWeight 1];//先遍历物品再遍历背包作为01背包处理for (int i 0; i n; i) {for (int j bagWeight; j weight[i]; j--) {//遍历每种物品的个数for (int k 1; k nums[i] (j - k * weight[i]) 0; k) {dp[j] Math.max(dp[j], dp[j - k * weight[i]] k * value[i]);}}}System.out.println(dp[bagWeight]);}
}leetcode139. 单词拆分
class Solution {public boolean wordBreak(String s, ListString wordDict) {//dp[i] : dp[i] : 字符串长度为i的话dp[i]为true表示可以拆分为一个或多个在字典中出现的单词。SetString wordSet new HashSet(wordDict);boolean[] dp new boolean[s.length() 1];dp[0] true;for(int i 1;is.length();i){ //背包for(int j 0;ji;j){//物品if(dp[j] wordSet.contains(s.substring(j,i))){dp[i] true;break;}} }return dp[s.length()];}
}
