锐客网

  1. 首页 > it技术 > >

java|混合背包问题

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; } }

    推荐阅读


    上一篇：protobuf的基本使用（读取和写入）——java

    下一篇：java spi实例