الگوریتم این سوال
سلام دوستان عزیز
این سوال رو من خیلی روش فکر کردم منتها فک کنم به الگوریتم بازگشتی نیاز داره ولی هرکاری کردم حل نشد میشه بیزحمت نحوه حلش رو بفرمایید تشکر
بله الان مجدد چک کردم دیدم روشم اشتباه بود، تلاشم این بود که راه بهینه تری ارائه کنم که موفق نبود
این کد تمام حالت های ممکن رو چک میکنه به همین دلیل بهینه نیست ولی فکر میکنم جواب درست تولید کنه
public $total = 1000;
public $coins = [100,300,500];
public $sum=[];
function rec($array,$total,$old){
foreach ($array as $key=>$value){
unset($array[$key]);
for($i=floor($total/$value);$i>=0;$i--){
$remain = $total-$i*$value;
$old[$value]= $i;
if ($remain==0){
if (array_sum($old) >0){
$this->sum[implode(",",array_keys($old))."-".implode(",",array_values($old))] = $old;
}
$old =[];
}
elseif($remain<0){
$old =[];
}
$this->rec($array,$remain,$old);
}
}
}
public function test()
{
$this->rec($this->coins,$this->total,[]);
echo json_encode($this->sum);
}خروجی:
{
"100-10":{
"100":10
},
"100,300-7,1":{
"100":7,
"300":1
},
"100,300,500-5,0,1":{
"100":5,
"300":0,
"500":1
},
"100,300-4,2":{
"100":4,
"300":2
},
"100,300,500-2,1,1":{
"100":2,
"300":1,
"500":1
},
"100,300-1,3":{
"100":1,
"300":3
},
"100,300,500-0,0,2":{
"100":0,
"300":0,
"500":2
}
}
بزرگترین a که از n کوچکتر هست رو پیدا کن
از n
a رو کم کن
همین کار رو، روی n باقی مانده انجام بده
حالا اگه در نهایت n صفر شد، که امکان پذیره، اگه نه هم که امکان پذیر نیست
درباره ج) نظری ندارم
خب عزیز مشکله اینه که میتونیم مثلا ۵ تا سکه a1 استفاده کنیم محدودیتی برای تعداد استفاده از یک سکه نیست یک مثال ساده میزنم یه اسکناس ۱۰۰۰ داریم میخایم با سکه ۲۰۰ و ۳۰۰ خورد کنیم برا همین میتونیم ۵تا۲۰۰ تومنی استفاده کنیم یا ۲تا۳۰۰تومنی با ۲ تا ۲۰۰ تومنی منظورم اینجوریه واقعا بدجور درگیرشم ممنون میشم کمک کنین
@IrajJavidan1 @farhadi @mehranmarandi90 @Alimotreb @ali.bayat @mehdi.mahdavi97 @ajdar9667 @gomnam
این کد با کال کردن متد test() میتونه خروجی رو تولید کنه
public $total = 1000;
public $coins = [100,200,500];
public $sum=[];
function recursive($old,$index,$count,$total){
$remain = $total-($this->coins[$index]*$count);
if ($count>0){
$old = $old ." | ".$this->coins[$index]." * ".$count;
}
if ($remain==0){
$this->sum[]=trim($old," |");
$old ='';
if ($count >1){
$this->recursive($old,$index,$count-1,$this->total);
}if ($index>0){
$index--;
$count = round($this->total/$this->coins[$index]);
for($j=$count;$j>=0;$j--){
$this->recursive($old,$index,$j,$this->total);
}
}
}elseif ($remain < 0){
$old ='';
if ($count>1){
$this->recursive($old,$index,$count-1,$this->total);
}elseif ($index>0){
$index--;
$count = floor($this->total/$this->coins[$index]);
$this->recursive($old,$index,$count,$this->total);
}
}elseif ($remain > 0){
if ($index>0){
$index--;
$count = floor($remain/$this->coins[$index]);
for($j=$count;$j>=0;$j--){
$this->recursive($old,$index,$j,$remain);
}
}
}
}
public function test()
{
$index = count($this->coins)-1;
$count = round($this->total/$this->coins[$index]);
$this->recursive("",$index,$count,$this->total);
echo json_encode($this->sum).PHP_EOL;
echo count($this->sum)>0?"امکان پذیر است ":"خیر امکان پذیر نیست".PHP_EOL;
echo count($this->sum) . "تعداد روش های انجام: ".PHP_EOL;
}یه هچین خرویجی تولید میشه
[
"500 * 2",
"500 * 1 | 200 * 2 | 100 * 1",
"500 * 1 | 200 * 1 | 100 * 3",
"500 * 1 | 200 * 0 | 100 * 5",
"200 * 5",
"200 * 4 | 100 * 2",
"100 * 10",
"200 * 4 | 100 * 2",
"200 * 3 | 100 * 4",
"200 * 2 | 100 * 6",
"200 * 1 | 100 * 8",
"100 * 10"
]"
امکان پذیر است
12تعداد روش های انجام":مهران جان واقعا تشکر از وقتی که گذاشتی ولی مثلا من سکه 200 تومنی و 300 تومنی میزنم مثلا دوتا 200 و 2 تا 300 رو حساب نمی کنه @mehranmarandi90
بله الان مجدد چک کردم دیدم روشم اشتباه بود، تلاشم این بود که راه بهینه تری ارائه کنم که موفق نبود
این کد تمام حالت های ممکن رو چک میکنه به همین دلیل بهینه نیست ولی فکر میکنم جواب درست تولید کنه
public $total = 1000;
public $coins = [100,300,500];
public $sum=[];
function rec($array,$total,$old){
foreach ($array as $key=>$value){
unset($array[$key]);
for($i=floor($total/$value);$i>=0;$i--){
$remain = $total-$i*$value;
$old[$value]= $i;
if ($remain==0){
if (array_sum($old) >0){
$this->sum[implode(",",array_keys($old))."-".implode(",",array_values($old))] = $old;
}
$old =[];
}
elseif($remain<0){
$old =[];
}
$this->rec($array,$remain,$old);
}
}
}
public function test()
{
$this->rec($this->coins,$this->total,[]);
echo json_encode($this->sum);
}خروجی:
{
"100-10":{
"100":10
},
"100,300-7,1":{
"100":7,
"300":1
},
"100,300,500-5,0,1":{
"100":5,
"300":0,
"500":1
},
"100,300-4,2":{
"100":4,
"300":2
},
"100,300,500-2,1,1":{
"100":2,
"300":1,
"500":1
},
"100,300-1,3":{
"100":1,
"300":3
},
"100,300,500-0,0,2":{
"100":0,
"300":0,
"500":2
}
}