【算法】【回溯篇】第7节:0 1背包问题

本期任务:介绍算法中关于回溯思想的几个经典问题 【算法】【回溯篇】第1节:八皇后问题 【算法】【回溯篇】第2节:解数独问题 【算法】【回溯篇】第3节:正则表达式问题 【算法】【回溯篇】第4节:全排列问题 【算法】【回溯篇】第5节:组合问题 【算法】【回溯篇】第6节:子集问题 【算法】【回溯篇】第7节:0-1背包问题 一、问题描述 给定n种物品和一背包。物品i的重量是wi>0,其价值为vi>0,背包的容量为c。 问应如何选择装入背包中的物品,使得装入背包中物品的总价值最大? (要求使用回溯法) 输入: n, c = 4, 7 w = [3, 5, 2, 1] v = [9, 10, 7, 4]