Skip to content

Files

Latest commit

e778296 · Sep 11, 2019

History

History
This branch is up to date with huihut/interview:master.

KnapsackProblem

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Feb 10, 2018
Sep 11, 2019
Feb 10, 2018

背包问题

代码

背包问题代码

问题说明

有N件物品和一个容量为V的背包。

第i件物品的重量是w[i],价值是v[i]。

求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,

且价值总和最大。

功能说明

本程序用动态规划的思想解决了背包问题,并用了两种算法: 迭代法、递归法。在迭代法中实现了打印背包问题的表格。

代码简述

通过用户输入数据,程序输入检测,动态分配空间,选择算法, 用动态规划的思想求解背包问题。

迭代法:

通过遍历n行W列,迭代每行每列的值,并把最优解放到 n行(在数组中为第n+1行)W列(在数组中为第W+1列)中。

递归法:

通过每次返回前i个物品和承重为j的最优解, 递归计算总背包问题的最优解。