الگوریتم این سوال
پاسخها
9
بله الان مجدد چک کردم دیدم روشم اشتباه بود، تلاشم این بود که راه بهینه تری ارائه کنم که موفق نبود
این کد تمام حالت های ممکن رو چک میکنه به همین دلیل بهینه نیست ولی فکر میکنم جواب درست تولید کنه
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
گفتگوهای مرتبط
شاید پاسخ شما همینجا باشد
@behzadi گفتم که،
درباره ج نظری ندارم
روشی که گفتم اشتباهه
این کد با کال کردن متد 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
@mehranmarandi90 اگر امکان داره یه راه ارتباطی هم معرفی کنین ممنون میشم
سلام دوستان. یه سوال قبل این سوالم ببینید .ثواب داره😓 سوال مرتب سازی آرایه شی