思路:背包(dp)
也就是最朴素的01背包问题
dp[j]就表示当下表为j的时候所能装载 的最大数量,可以得到dp的状态转移方程
dp[j]=max(dp[j],dp[j-a[i]]+1);(i从1~n 也就是所有的物品)
思路:贪心
想法:每次都选择重量最小的添加到其中
dp:
贪心:
dp的时间复杂度复杂度O(n*log n)//n是背包的数目,m背包的容量
贪心的时间复杂度O(n*logn)
GitHub
原文:https://www.cnblogs.com/passawayy/p/14777261.html