検索

比如
a物品价值1,
b物品价值2,
c物品价值8,
d物品价值10

我给出一个数字 30
求可能的组合

要求为所用到的物品最少,可重复

回复内容:

比如
a物品价值1,
b物品价值2,
c物品价值8,
d物品价值10

我给出一个数字 30
求可能的组合

要求为所用到的物品最少,可重复

@Ukyoi_D 同学的分析很对,只是后面提出的BFS求解剪枝方法并非动态规划的常见方法,当然,方法也是正确的。

首先规范一下原题:

有n个物品,每个物品的价值为v[i],且 v[0]

算法是动态规划,证明过程Ukyoi_D 同学已经证明了。这里给出状态转移方程。

状态转移方程为:

<code> f[i][w] = min{
   f[i-1][w] if f[i-1][w] exist 
   , 
   f[i-1][w-v[i]] +1 if f[i-1][w-v[i]]exist
  }</code>

其中f[i][w]代表在前i个物品中凑足w价值的物品需要的物品数量,f[i][w]存在表示前i个物品可以组合出w价值的物品,不存在表示不能组合出w价值的物品。

对于 f[i][w] 实际上存在3种可能,1. 选i物品,则需要物品数等于f[i-1][w-v[i]]+1。2. 不选i物品,则需要物品等于f[i-1][w], 3. f[i-1][w-v[i]]f[i-1][w]都不存在,则f[i][w]必然也不存在。

三种情况中选出最小的,或者不存在。

具体实现上只需要一个2维数组即可,不存在的状态用无穷大表示。

这个应该不涉及到算法啥的,要求所用到的物品最少,那就是尽量使用价值大的物品,
用30从d-》a取整,取余,整数就是当前的要用多少个,余数是剩下的,继续往下运算,直到分配完为止

//===============================
先看一下问题:
1、没说30一定要分配完
2、要求物品最少

所以我觉得我给出解法没什么问题,勉强算贪心算法

大家都说是背包问题,我认为不是
1、背包问题是两个维度考虑,重量和价值而这里只有价值
2、背包问题要求最后价值最大化,这里仅要求物品最少

问题描述:

<code>有m个物品, 价值从小到大 为V1 - Vm 
f(i) 为 "价值i且物品最少的组合"的 物品数
求解 f(n)
</code>

初始化

<code>f(0) = 0
f(i) = +∞,1 </code>

求解:

<code>从 1到 n
f(i) = min(f(i - Vx) {1 = Vx}) + 1 
如果不满足 1 = Vx, f(i) = +∞</code>

所用到的物品最少,可重复

那就是三个 d,刚好 30。

还有比这个更少的吗?

另外,这个根本不是背包问题啊,背包问题不仅有价值限制,还有重量限制的啊。

楼上说这个问题“不涉及算法”显然是不对的……这是一个多么经典的动态规划入门题……
贪心解对30这个特定的值是可行,但比如对16就是不可行的,16的最优解显然是拿两个8,而不是贪心法的先拿10再拿三个2。

原题中要用最少的物品凑够30,假如我先随便拿一个,比如我拿了一个2,接下来我还要拿28才能满足“凑够30”的要求,于是就出现了一个子问题:如何用最少物品凑够28。同理如果我拿了一个10,子问题就是我需要凑够20。

这个题目的关键在于所谓的“最优子结构”:当且仅当子问题的解是最优的,母问题的解才是最优的。举例而言,拿第一个东西我可以有1、2、8、10四种选择,于是这个问题变成四个子问题,假如我已经知道了四个子问题中的某一个的答案是这四个子问题中所拿东西最少的,就比如说需要拿k个吧,那么加上刚才拿的第一个,那么原问题就最少需要k+1个。当然实际上我们还不知道这4个子问题究竟哪个的解是最优的,所以就采用递归的方法,对四个子问题分别再求子问题,找到所有的二级子问题。在所有二级子问题之中,假如存在一个最优解,比如需要拿m个,那么同理,一级子问题的解就是至少要拿m+1个,而母问题的解就是要拿m+2个。最优子结构是动态规划实现的基础。

具体算法的实现请看 bluedream 君的解答,那个是动态规划的标准方法。我下面给出的解答用了递归,计算机需要更多资源来处理函数调用,而且通常也更慢。


广度优先搜索解法:

刚才的推理建立在“假如知道子问题的解”,当然二级子问题的解实际还是不知道,那就继续往下找。就这么像剥洋葱一样层层剥开(黑话叫“广度优先搜索”)。(这里有个小trick:先拿8再拿2和先拿2再拿8是一样的,优化掉后可以省一小半资源)

求到若干层之后,比如有一条路线最新的子问题要求拿满8,此时显然拿一个8就是这个子问题的最优解。那么别的路线都可以不用算了,因为别的路线最少也得再拿一个才满足要求。顺着这个找到的最优解一层一层退回去,就找到了整个问题的最优解(之一)。当然也可能某个路线最后发现无解(本题不可能,因为能拿1,总能用1凑够任何一个正整数,但如果原题目要求拿30块零5毛那么显然无解),那就舍弃这个路线,继续找其它的路线,直到找到解。或者遍历所有可能的情况发现无解。

当然上面是“广度优先”的方法,也可以用“深度优先”的方法,就是说像走迷宫一样,先顺着其中一个子问题(以及这个子问题的子问题)一条道走到黑,如果是死胡同再退回来,换一条路,这个时候找到的第一个解未必是最优解,但是有了这个解的参照,所有比这个解还要深的胡同就可以都标记成死路,不用再钻了,因为最优解的步骤比刚发现的那个肯定只少不多。如果之后又发现了更优解,就以这个更优的解作新的参照……这样钻过所有的路之后,要么一个最优解也没发现,要么最新发现的解就是最优解。

首先,所有手算结果的回答显然是错误的。
题主拿这个只是举个例子,实际情况当然物品价值和要求解的价值都是程序输入。
不可能手算出一个结果就说这题没意义了。

其次,上面@ekea0407 所说的贪心解法是错误的。
假设物品重量按题目说是1,2,8,10,要求解的重量是16,这个时候按贪心算法:
16=10+6=10+2+4=10+2+2+2,变成4件物品。
其实16=8+8,只需要2件物品。

最后,这个问题和背包问题还是有点区别吧,只是都用动态规划求解,求解过程也类似。
@brayden 的解法就行。
用暴力搜索遍历解空间的解法是很差的,因为暴力搜索没有把已经找到过的局部解存储下来,会多次求解同一问题。
这个题还是用动态规划合适。

感觉楼主这个问题几乎不涉及算法. 先用3个10,直接30了.如果有不用10的话,直接就比3个多了,问题就没有进行下去的必要了.

背包问题
动态规划

这是背包问题,上面一位同学说这个不涉及到算法,其实是不科学的。题主可以网上搜索一下楼教主的‘背包九讲’,这个问题就迎刃而解了。

声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
PHPおよびPython:さまざまなパラダイムが説明されていますPHPおよびPython:さまざまなパラダイムが説明されていますApr 18, 2025 am 12:26 AM

PHPは主に手順プログラミングですが、オブジェクト指向プログラミング(OOP)もサポートしています。 Pythonは、OOP、機能、手続き上のプログラミングなど、さまざまなパラダイムをサポートしています。 PHPはWeb開発に適しており、Pythonはデータ分析や機械学習などのさまざまなアプリケーションに適しています。

PHPとPython:彼らの歴史を深く掘り下げますPHPとPython:彼らの歴史を深く掘り下げますApr 18, 2025 am 12:25 AM

PHPは1994年に発信され、Rasmuslerdorfによって開発されました。もともとはウェブサイトの訪問者を追跡するために使用され、サーバー側のスクリプト言語に徐々に進化し、Web開発で広く使用されていました。 Pythonは、1980年代後半にGuidovan Rossumによって開発され、1991年に最初にリリースされました。コードの読みやすさとシンプルさを強調し、科学的コンピューティング、データ分析、その他の分野に適しています。

PHPとPythonの選択:ガイドPHPとPythonの選択:ガイドApr 18, 2025 am 12:24 AM

PHPはWeb開発と迅速なプロトタイピングに適しており、Pythonはデータサイエンスと機械学習に適しています。 1.PHPは、単純な構文と迅速な開発に適した動的なWeb開発に使用されます。 2。Pythonには簡潔な構文があり、複数のフィールドに適しており、強力なライブラリエコシステムがあります。

PHPとフレームワーク:言語の近代化PHPとフレームワーク:言語の近代化Apr 18, 2025 am 12:14 AM

PHPは、多数のWebサイトとアプリケーションをサポートし、フレームワークを通じて開発ニーズに適応するため、近代化プロセスで依然として重要です。 1.PHP7はパフォーマンスを向上させ、新機能を紹介します。 2。Laravel、Symfony、Codeigniterなどの最新のフレームワークは、開発を簡素化し、コードの品質を向上させます。 3.パフォーマンスの最適化とベストプラクティスは、アプリケーションの効率をさらに改善します。

PHPの影響:Web開発などPHPの影響:Web開発などApr 18, 2025 am 12:10 AM

phphassiblasifly-impactedwebdevevermentandsbeyondit.1)itpowersmajorplatformslikewordpratsandexcelsindatabase interactions.2)php'sadaptableability allowsitale forlargeapplicationsusingframeworkslikelavel.3)

スカラータイプ、リターンタイプ、ユニオンタイプ、ヌル可能なタイプなど、PHPタイプのヒントはどのように機能しますか?スカラータイプ、リターンタイプ、ユニオンタイプ、ヌル可能なタイプなど、PHPタイプのヒントはどのように機能しますか?Apr 17, 2025 am 12:25 AM

PHPタイプは、コードの品質と読みやすさを向上させるためのプロンプトがあります。 1)スカラータイプのヒント:php7.0であるため、基本データ型は、int、floatなどの関数パラメーターで指定できます。 3)ユニオンタイプのプロンプト:PHP8.0であるため、関数パラメーターまたは戻り値で複数のタイプを指定することができます。 4)Nullable Typeプロンプト:null値を含めることができ、null値を返す可能性のある機能を処理できます。

PHPは、オブジェクトのクローニング(クローンキーワード)と__Clone Magicメソッドをどのように処理しますか?PHPは、オブジェクトのクローニング(クローンキーワード)と__Clone Magicメソッドをどのように処理しますか?Apr 17, 2025 am 12:24 AM

PHPでは、クローンキーワードを使用してオブジェクトのコピーを作成し、\ _ \ _クローンマジックメソッドを使用してクローン動作をカスタマイズします。 1.クローンキーワードを使用して浅いコピーを作成し、オブジェクトのプロパティをクローン化しますが、オブジェクトのプロパティはクローニングしません。 2。\ _ \ _クローン法は、浅いコピーの問題を避けるために、ネストされたオブジェクトを深くコピーできます。 3.クローニングにおける円形の参照とパフォーマンスの問題を避けるために注意し、クローニング操作を最適化して効率を向上させます。

PHP対Python:ユースケースとアプリケーションPHP対Python:ユースケースとアプリケーションApr 17, 2025 am 12:23 AM

PHPはWeb開発およびコンテンツ管理システムに適しており、Pythonはデータサイエンス、機械学習、自動化スクリプトに適しています。 1.PHPは、高速でスケーラブルなWebサイトとアプリケーションの構築においてうまく機能し、WordPressなどのCMSで一般的に使用されます。 2。Pythonは、NumpyやTensorflowなどの豊富なライブラリを使用して、データサイエンスと機械学習の分野で驚くほどパフォーマンスを発揮しています。

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

このプロジェクトは osdn.net/projects/mingw に移行中です。引き続きそこでフォローしていただけます。 MinGW: GNU Compiler Collection (GCC) のネイティブ Windows ポートであり、ネイティブ Windows アプリケーションを構築するための自由に配布可能なインポート ライブラリとヘッダー ファイルであり、C99 機能をサポートする MSVC ランタイムの拡張機能が含まれています。すべての MinGW ソフトウェアは 64 ビット Windows プラットフォームで実行できます。

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

WebStorm Mac版

WebStorm Mac版

便利なJavaScript開発ツール

Dreamweaver Mac版

Dreamweaver Mac版

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)