think: 1 01背包 2 注意c[]數組和w[]數組的輸入順序
sdut原題鏈接
Bone Collector Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave … The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?
Input The first line contain a integer T , the number of cases. Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.
Output One integer per line representing the maximum of the total value (this number will be less than 231).
Example Input 1 5 10 1 2 3 4 5 5 4 3 2 1
Example Output 14
Hint hdoj2602
Author
以下為accepted代碼
#include <stdio.h>#include <string.h>#define Max(a, b) (a > b? a: b)int main(){ int T, n, v, c[1004], w[1004], dp[1004]; scanf("%d", &T); while(T--) { memset(dp, 0, sizeof(dp)); scanf("%d %d", &n, &v); for(int i = 0; i < n; i++) { scanf("%d", &w[i]); } for(int i = 0; i < n; i++) { scanf("%d", &c[i]); } for(int i = 0; i < n; i++) { for(int j = v; j >= c[i]; j--) { dp[j] = Max(dp[j], dp[j-c[i]] + w[i]); } } printf("%d/n", dp[v]); } return 0;}/***************************************************User name: Result: AcceptedTake time: 0msTake Memory: 120KBSubmit time: 2017-02-18 16:44:33****************************************************/新聞熱點
疑難解答
