【UVa】10819 - Trouble of 13-Dots
Problem here
Problem
Do you know 13-Dots? She is the main character of a well-known Hong Kong comic series. She is famous of her beauty, as well as the variety of stylish clothes she wears. Now 13-Dots is facing a problem. She used to have a large amount of pocket money every month. However, her father has decided to cut down her budget of buying new clothes! In the past, she would buy every dress she liked without hesitation, but now she needs careful consideration before making any purchase. Every month, she prepares a list containing the prices and ’favour indices’ (ranging from 1 to 5) of all items she is interested. At the end of the month, she would decide how to spend her money such that the total favour value is maximized. It is important to know that 13-Dots always uses her credit card to pay the bill, which offers her a 200-dollar refund if her total expense in the month exceeds 2000.Forexample,ifherbudgetis 5000, she can buy clothes with total marked price of at most 5200 dollars. Since the optimal way is hard to be figured out just by hand, can you write a program for 13-Dots that helps her make the decision? Remember that you should NEVER select an item more than once, even if this leads to a greater total favour value.
INPUT
The input consists of several test cases. Each of them has the following format: The first line gives two integers, m and n (0 ≤ m ≤ 10000, 0 ≤ n ≤ 100), which are the amount of pocket money 13-Dots has and the number of items on the list respectively. The following n lines each contains two integers, p and f (0 < p ≤ 4000, 1 ≤ f ≤ 5), where p is the marked price of the item, and f is its ‘favour index’. Input is terminated by EOF.
OUTPUT
For each test case, print one line giving the maximum total favour value 13-Dots can get.
SAMPLE
input
500 4 100 2 100 3 200 3 400 4
output
8
Solution
Problem
Do you know 13-Dots? She is the main character of a well-known Hong Kong comic series. She is famous of her beauty, as well as the variety of stylish clothes she wears. Now 13-Dots is facing a problem. She used to have a large amount of pocket money every month. However, her father has decided to cut down her budget of buying new clothes! In the past, she would buy every dress she liked without hesitation, but now she needs careful consideration before making any purchase. Every month, she prepares a list containing the prices and ’favour indices’ (ranging from 1 to 5) of all items she is interested. At the end of the month, she would decide how to spend her money such that the total favour value is maximized. It is important to know that 13-Dots always uses her credit card to pay the bill, which offers her a 200-dollar refund if her total expense in the month exceeds 2000.Forexample,ifherbudgetis 5000, she can buy clothes with total marked price of at most 5200 dollars. Since the optimal way is hard to be figured out just by hand, can you write a program for 13-Dots that helps her make the decision? Remember that you should NEVER select an item more than once, even if this leads to a greater total favour value.
INPUT
The input consists of several test cases. Each of them has the following format: The first line gives two integers, m and n (0 ≤ m ≤ 10000, 0 ≤ n ≤ 100), which are the amount of pocket money 13-Dots has and the number of items on the list respectively. The following n lines each contains two integers, p and f (0 < p ≤ 4000, 1 ≤ f ≤ 5), where p is the marked price of the item, and f is its ‘favour index’. Input is terminated by EOF.
OUTPUT
For each test case, print one line giving the maximum total favour value 13-Dots can get.
SAMPLE
input
500 4 100 2 100 3 200 3 400 4
output
8
Solution
#include <iostream>
#include "memory.h"
using namespace std;
int p[4001], f[4001];
int dp[110][11000];
int n, m;
int sf(int i, int w){
if(w > m && m <= 1800)
return -1000;
if(w > m+200)
return -1000;
if(i == n){
if(w > m && w <= 2000)
return -1000;
return 0;
}
if(dp[i][w] != -1){
return dp[i][w];
}
return dp[i][w] = max(sf(i+1, w), sf(i+1, w+p[i]) + f[i]);
}
int main(){
while(cin >> m >> n){
memset(p, 0, sizeof(p));
memset(f, 0, sizeof(f));
memset(dp, -1, sizeof(dp));
for(int i = 0; i < n; i++){
int ip, fi;
cin >> ip >> fi;
p[i] = ip;
f[i] = fi;
}
cout << sf(0, 0) << endl;
}
return 0;
}