java|混合背包问题算法|动态规划

【java|混合背包问题】原题链接：https://www.acwing.com/problem/content/7/
注：方法都是根据闫学灿的DP分析法得到的，欢迎大家去B站搜索原视频。
有 N 种物品和一个容量是 V 的背包。
物品一共有三类：
第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 si 次（多重背包）；
每种体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
si=?1 表示第 i 种物品只能用1次；
si=0 表示第 i 种物品可以用无限次；
si>0 表示第 i 种物品可以使用 si 次；
输出格式
输出一个整数，表示最大价值。
数据范围
0 0 ?1≤si≤1000
输入样例
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
输出样例：
8

import java.util.*; // 思路 /* 将整个问题化为两类 01背包问题和完全背包问题怎么将多重背包问题转为成01背包问题 ---> 二进制优化因为要分为两种类型，我们可以用一个数据结构来记录每种物品的类型再去通过类型选择不同的选择策略 */ public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int N = in.nextInt(), V = in.nextInt(); Deque deque = new LinkedList(); int[] f = new int[V+1]; for(int i = 1; i <= N; i++){ int v = in.nextInt(); int w = in.nextInt(); int kind = in.nextInt(); if(kind < 0){ deque.addLast(new Thing(-1, v, w)); } else if(kind == 0){ deque.addLast(new Thing(0, v, w)); } else{ for(int k = 1; k <= kind; k *= 2){ kind -= k; deque.addLast(new Thing(-1, k * v, k * w)); } if(kind > 0){ deque.addLast(new Thing(-1, kind * v, kind * w)); } } } for(Thing thing : deque){ if(thing.kind == -1){// 转化成了01背包问题 for(int j = V; j >= thing.v; j--){ f[j] = Math.max(f[j], f[j - thing.v] + thing.w); } } else if(thing.kind == 0){ //完全背包问题 for(int j = thing.v; j <= V; j++){ f[j] = Math.max(f[j], f[j - thing.v] + thing.w); } } } System.out.println(f[V]); } }class Thing{ int kind; int v,w; public Thing(int kind, int v,int w){ this.kind = kind; this.v = v; this.w = w; } }

java|混合背包问题

推荐阅读

电商模式 mv是电商的什么，电商平台

蓝光驱蚊灯可以和人在一起吗

兼职跨境电商怎么样跨境电商可以做什么兼职，哪个跨境电商平台适合兼职做

香菇酿肉的方法

方牌玉件的佩戴方法方形玉牌吊坠怎么佩戴

纳兰词全集及赏析温室的花

cdrx8安装提示已安装另一个版本解决方法

win10自带硬盘安装系统怎么安装，win10自带硬盘安装系统怎么安装不了

微信没声音怎么回事没有声音解决办法

智齿|智齿发炎，疼痛得厉害还不能拔牙，有什么应急措施？

人工智能论文，人工智能的发展前景及其应用的论文怎么写

北太行在什么地方北太行在哪里

博世壁挂炉德国还土耳其原因？

2023款一汽大众辉腾一汽大众辉腾字母

3点到5点醒是癌症征兆有科学依据吗

樟脑丸可以放床下吗

干燥综合征如何治疗?

建设自由贸易区的意义 12个自贸试验区共有哪些

儿童可以使用免洗洗手液吗

登鹳雀楼古诗看到了哪四种景物？