状态及状态转移的定义

来源：9-5 0-1背包问题

慕粉3924834

2018-04-18

老师，你好.我将状态以及状态转移定义成下面这种形式可以吗

F（n，C）=max ( v(0)+F( n-1,C-w(0) ) , v(1)+F( n-1,C-w(1) ) , v(2)+F( n-1,C-w(2) ) ........ v(i)+F( n-1,C-w(1) ) ,v(n-1)+F( n-1,C-w(n-1) ) )

将F（n，C）的问题转换成F(n-1,C-w(i)), 递归终止的条件就是当选择的物品重量＞背包剩余容量的时候，递归并不是都要递归到底，所以有些物品也就没有办法放入背包，请老师原谅我编码能力实在太差...

写回答

1回答

liuyubobobo

2018-04-19

似乎有一些问题，你的状态转移中，每次都一定会拿出一个物品，最终得到的是这些物品的一个排列。但是背包问题的解释物品的组合，是选择拿哪些物品，不拿哪些物品。

或者可能我没有完全理解你的思路？把代码写出来试试看？：）

liuyubobobo

慕粉3924834

对。准确的说是没有重叠子问题：）

2018-04-19

共4条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7410 学习 · 1150 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1