開心的小明

時間限制： 1000 ms  |  記憶體限制： 65535 KB 難度： 4

描述

小明今天很開心，家裡購置的新房就要領鑰匙了，新房裡有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎麼布置，你說了算，隻要不超過N 元錢就行”。今天一早小明就開始做預算，但是他想買的東西太多了，肯定會超過媽媽限定的N 元。于是，他把每件物品規定了一個重要度，分為5 等：用整數1~5 表示，第5 等最重要。他還從網際網路上查到了每件物品的價格（都是整數元）。他希望在不超過N 元（可以等于N 元）的前提下，使每件物品的價格與重要度的乘積的總和最大。設第j 件物品的價格為v[j]，重要度為w[j]，共選中了k 件物品，編号依次為j1...jk，則所求的總和為：v[j1]*w[j1]+..+v[jk]*w[jk]請你幫助金明設計一個滿足要求的購物單.

輸入

第一行輸入一個整數N(0<N<=101)表示測試資料組數

每組測試資料輸入的第1 行，為兩個正整數，用一個空格隔開：

N m

（其中N（<30000）表示總錢數，m(<25)為希望購買物品的個數。）

從第2 行到第m+1 行，第j 行給出了編号為j-1

的物品的基本資料，每行有2 個非負整數

v p

（其中v 表示該物品的價格（v≤10000），p 表示該物品的重要度（1~5））

輸出

每組測試資料輸出隻有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的

最大值（<100000000）

樣例輸入

1
1000 5
800 2
400 5
300 5
400 3
200 2      

樣例輸出

3900      

簡單的01背包問題，不過把老師兩個月前教的動态規劃忘得一幹二淨，罪過罪過。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
struct node{
	int value;
	int num;
}p[26];
int main(void){
 //freopen("題.txt", "r", stdin);
 	int t, n, m;
 	int arr[30001];
 	scanf("%d", &t);
 	while(t--){
 		memset(arr, 0, sizeof(arr));
 		scanf("%d%d", &m, &n);
 		for(int i = 1; i <= n; i++){
 			scanf("%d%d", &p[i].value, &p[i].num);
		}		
		
		for(int i = 1; i <= n; i++){
			for(int j = m; j >= p[i].value; j--){
				arr[j] = max(arr[j], arr[j-p[i].value] + p[i].value * p[i].num);
			}	
		}
		printf("%d\n",arr[m]);
	 }
	
    return 0;
}