Asked Oct 9th, 2017 8:31 AM 341 0 1
  • 341 0 1
0

Giải quyết bài toán quy hoạch động.

Share
  • 341 0 1

Hi các bạn, Mình có bài toán như thế này:

Cho một mảng : 
$list = [3, 3, 6,6,16,11,11,11,16,4,4,4];
Tính tất cả các cách chọn ra số lượng các phần tử trong mảng sao cho tổng lớn hơn hoặc bằng tổng S = 64?

Mình có tìm hiểu thì dùng thuật toán Quy Hoạch động, nhưng thử mãi vẫn chưa được. Các bạn giúp mình cái hướng xử lý bài toán này với nhé. Mình có dùng cách cổ điển là dùng các vòng For nhưng thời gian tính toán lâu quá 😦 (mình dùng PHP)

for($i1 = $Ui/3;$i1 >=0; $i1--)
	{
		$j2 = $Ui - $i1 * 3;
		for($i2 = $j2/3;$i2 >=0; $i2--)
		{
			$j3 = $j2 - $i2 * 3;
			for($i3 = $j3/6;$i3 >=0; $i3--)
			{
				$j4 = $j3 - $i3*6;
				for($i4 = $j4/6; $i4 >= 0; $i4--)
				{
					$j5 = $j4 - $i4 * 6;
					for($i5 = $j5/16; $i5 >=0; $i5--)
					{
						$j6 = $j5 - $i5 * 16;
						for($i6 = $j6/11; $i6 >=0; $i6--)
						{
							$j7 = $j6 - $i6*11;
							for($i7 = $j7/11; $i7 >= 0; $i7--)
							{
								$j8 = $j7 - $i7*11;
								for($i8 = $j8/16; $i8 >= 0; $i8--)
								{
									$j9 = $j8 - $i8*11;
									for($i9 = $j9/4; $i9 >= 0; $i9--)
									{
										$j10 = $j9 - $i9*4;
										for($i10 = $j10/4; $i10 >= 0; $i10--)
										{
											$j11 = $j10 - $i10*4;
											for($i11 = $j11/4; $i11 >= 0; $i11--)
											{
												$tong = ROUND($i1)*3 + ROUND($i2)*3 + ROUND($i3)*6 + ROUND($i4)*6 + ROUND($i5)*16 + ROUND($i6)*11 + ROUND($i7)*11 + ROUND($i8)*16 + ROUND($i9)*4 + ROUND($i10)*4 + ROUND($i11)*4;
												
												if($tong >= $Ui)
												{
													echo'kq thu: '.$r.' tai lan tinh thu:'.$s.': ';
													echo 'Ui: '.ROUND($i1).'*3 + '.ROUND($i2).'*3 + '.ROUND($i3).'*6 + '.ROUND($i4).'*6 +'.ROUND($i5).'*16 +'.ROUND($i6).'*11 + '.ROUND($i7).'*11 + '.ROUND($i8).'*16 +'.ROUND($i9).'*4 + '.ROUND($i10).'*4 + '.ROUND($i11).'*4 ='.$tong.'<br/>';
													
												}
												
											}
										}
									}		
								}	
							}
						}
					}
				}
			}
		}	
	}

Cám ơn các bạn.

1 ANSWERS


Answered Oct 10th, 2017 7:51 AM
Accepted
+6

bạn có thể sử dụng quy hoạch động như sau:

  • Sử dụng một mảng counts[0..sum(arr)+1], trong đó counts[i] là số cách phân tích số i ra tổng của các số trong list
  • đặt counts[0] = 1, các phẩn tử khác là 0
  • duyệt qua một lượt các phần tử trong list, với mỗi arr[i], ta cập nhật lại mảng counts với các phần tử >= arr[i]:
counts[j] = counts[j] + counts[j - arr[i]]
  • Kết quả là tổng các phần tử của counts bắt đầu từ 64 trở lên

Sample Code:

arr = [3, 3, 6,6,16,11,11,11,16,4,4,4]
s = sum(arr)
n = len(arr)
counts = [0]*(s+1)
counts[0] = 1

for i in range(n):
  for j in range(s, arr[i]-1, -1):
    counts[j] += counts[j - arr[i]]
  #print counts
  
print sum(counts[64:])

Độ phức tạp O(sum*n). Nếu yêu cầu bài toán không tính lặp thì sẽ phải xử lý phức tạp hơn chút, và số lượng sẽ giảm đi do lặp các số giống nhau.

Share
Thịnh @Thinh.Tran
Oct 11th, 2017 2:46 AM

Cám ơn bạn Kiên, Mình đã dần hình dung ra được, nhưng nếu mình muốn in các trường hơp đúng thì như thế nào nhỉ? Dạng như:

17x3 + 3x3 + 1x6 + 0x6 +0x16 +0x11 + 0x11 + 0x16 +0x4 + 0x4 + 0x4 =66

Sory, mình không biết python nên hơi gà

0
| Reply
Share