分类：java动态规划

2021
09-13

Java实现动态规划背包问题

目录前言一、原理1.1最优子结构性质1.2递归关系二、算法描述2.1算法描述2.2图解2.3构造最优解三、0−10-10−1背包问题相关题目3.1题目3.2源程序(Java求解0−10-10−1背包问题)3.3运行结果总结前言给定nnn种物品和一个背包。物品iii的重量是wiwiwi，其价值为vivivi，背包的容量为ccc。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大？一、原理0−0... 继续阅读 >

2021
04-09

java背包问题动态规划算法分析

背包问题【题目描述】一个旅行者有一个最多能装MM公斤的背包，现在有nn件物品，它们的重量分别是W1，W2，…,WnW1，W2，…,Wn,它们的价值分别为C1,C2,…,CnC1,C2,…,Cn，求旅行者能获得最大总价值。【输入】第一行：两个整数，MM(背包容量，M<=200M<=200)和NN(物品数量，N<=30N<=30)；第2…N+12…N+1行：每行二个整数Wi，CiWi，Ci，表示每个物品的重量和价值。【输出】仅一行，一个数，表示最大总价值。【输入样例】10421334... 继续阅读 >