李春葆教授的算法设计与剖析
最编程
2024-07-30 22:39:50
...
本文已参与「新人创作礼」活动，一起开启掘金创作之路。
算法设计与分析练习题
（一） 0-1背包问题
1. 问题描述
题目：
给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.
输入格式
输入的第一行包含两个整数n, m，分别表示物品的个数和背包能装重量。
以后两行分别为每个物品的价值，重量
输出格式
输出2行，第一行包含一个整数，表示最大价值
第二行为装入背包的物品序号
样例输入
5 8
v[]={2,1,4,3,5};
w[]={1,4,2,3,5};
样例输出
装入背包中物品总价值最大为：
11
装入的物品的序号为：
1 3 5
数据规模和约定
1<=N<=200,M<=5000.
解题思路：
根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组...... 查看更多
上一篇： 李春葆的《数据结构》第一章节详解
下一篇： 算法设计与分析第二版李春葆课后习题答案