問答題
問題描述 李老師收集控,喜歡在旅行過程中收集各種不同物品。 有一次李老師旅行到了鄉(xiāng)間集市,集市上當(dāng)然也有各種各樣好玩的東西,而且每種物品隨便買,要多少有多少! 現(xiàn)在問題又來了: 給定每種物品的大小和價(jià)值,以及李老師的背包容量,李老師最多能帶走價(jià)值多少的物品?輸入: 多組輸入樣例,第一行一個(gè)整數(shù)T,代表輸入樣例數(shù)。 接下來的每個(gè)樣例: 第一行包含兩個(gè)正整數(shù)N , V, (N <= 1 2 3
答案:
這個(gè)問題描述的是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃問題,稱為“0-1背包問題”。在這個(gè)問題中,我們有一個(gè)背包和一些物品,每個(gè)物品都有自己...