發表新討論
#36989: 寫不出來在看(可能對各位沒用)


aa0980949726@gmail.com (統測戰士)

學校 : 國立華南高級商業職業學校
編號 : 224693
來源 : [220.142.154.91]
最後登入時間 ：
2024-10-02 15:43:20
k771. 請認真做好值日! -- 三國迷李牧粉題集 | From: [27.240.232.130] | 發表日期 : 2023-08-18 23:50

dp 背包問題

dp建表：

創建一個二維數組 dp，其中 dp[i][j] 表示使用前 j 個工作，在可用時間為 i 的情況下，能夠獲得的最大分數。
初始化 dp 數組，將所有元素初始化為 0。
填表過程：

使用兩個迴圈來遍歷工作和可用時間。
對於每個工作 j 和可用時間 i，判斷是否可以將該工作納入考慮。
如果 i 大於等於該工作的時間 z[j-1][0]，表示可以選擇這個工作。
此時 dp[i][j] 的值等於在選擇該工作和不選擇該工作中，選擇最大分數的情況。
否則， dp[i][j] 的值等於不選擇該工作的情況。
尋找最佳解：

從 dp 數組的最後一行開始，逐行檢查，找到第一個分數大於等於目標分數 m 的時間 i，即為答案。
同時， dp[i][-1] 就是在可用時間為 i 的情況下能夠達到的最大分數。

 
#36990: Re: 寫不出來在看(可能對各位沒用)


aa0980949726@gmail.com (統測戰士)

學校 : 國立華南高級商業職業學校
編號 : 224693
來源 : [220.142.154.91]
最後登入時間 ：
2024-10-02 15:43:20
k771. 請認真做好值日! -- 三國迷李牧粉題集 | From: [27.240.232.130] | 發表日期 : 2023-08-18 23:50

dp 背包問題

dp建表：

創建一個二維數組 dp，其中 dp[i][j] 表示使用前 j 個工作，在可用時間為 i 的情況下，能夠獲得的最大分數。
初始化 dp 數組，將所有元素初始化為 0。
填表過程：

使用兩個迴圈來遍歷工作和可用時間。
對於每個工作 j 和可用時間 i，判斷是否可以將該工作納入考慮。
如果 i 大於等於該工作的時間 z[j-1][0]，表示可以選擇這個工作。
此時 dp[i][j] 的值等於在選擇該工作和不選擇該工作中，選擇最大分數的情況。
否則， dp[i][j] 的值等於不選擇該工作的情況。
尋找最佳解：

從 dp 數組的最後一行開始，逐行檢查，找到第一個分數大於等於目標分數 m 的時間 i，即為答案。
同時， dp[i][-1] 就是在可用時間為 i 的情況下能夠達到的最大分數。

-------------------

----------------------

 

 

 

----------------------------------------

下面是程式碼

 
#36991: Re: 寫不出來在看(可能對各位沒用)


aa0980949726@gmail.com (統測戰士)

學校 : 國立華南高級商業職業學校
編號 : 224693
來源 : [220.142.154.91]
最後登入時間 ：
2024-10-02 15:43:20
k771. 請認真做好值日! -- 三國迷李牧粉題集 | From: [27.240.232.130] | 發表日期 : 2023-08-18 23:52

dp 背包問題

dp建表：

創建一個二維數組 dp，其中 dp[i][j] 表示使用前 j 個工作，在可用時間為 i 的情況下，能夠獲得的最大分數。
初始化 dp 數組，將所有元素初始化為 0。
填表過程：

使用兩個迴圈來遍歷工作和可用時間。
對於每個工作 j 和可用時間 i，判斷是否可以將該工作納入考慮。
如果 i 大於等於該工作的時間 z[j-1][0]，表示可以選擇這個工作。
此時 dp[i][j] 的值等於在選擇該工作和不選擇該工作中，選擇最大分數的情況。
否則， dp[i][j] 的值等於不選擇該工作的情況。
尋找最佳解：

從 dp 數組的最後一行開始，逐行檢查，找到第一個分數大於等於目標分數 m 的時間 i，即為答案。
同時， dp[i][-1] 就是在可用時間為 i 的情況下能夠達到的最大分數。

-------------------

----------------------

 

 

 

----------------------------------------

下面是程式碼

-------------------


 

 

n, m, o = map(int, input().split())
z = []
for i in range(o):
    x, i = map(int, input().split())
    z.append((x, i))
dp = [[0 for j in range(o+1)] for i in range(n+1)]
for j in range(1, o+1):
    for i in range(1, n+1):
        if i >= z[j-1][0]:
            dp[i][j] = max(dp[i][j-1], dp[i-z[j-1][0]][j-1] + z[j-1][1])
        else:
            dp[i][j] = dp[i][j-1]
for i in range(1, n+1):
    if dp[i][-1] >= m:
        print(i, dp[i][-1])
        break
有人有更好的方法也請私訊我，感謝
 
ZeroJudge Forum