动态规划 – 柳婼の blog

L3-001. 凑零钱-PAT团体程序设计天梯赛GPLT（01背包，动态规划）

韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里，发现这家店有个特别的规矩：你可以用任何星球的硬币付钱，但是绝不找零，当然也不能欠债。韩梅梅手边有104枚来自各个星球的硬币，需要请你帮她盘算一下，是否可能精确凑出要付的款额。

输入格式：

输入第一行给出两个正整数：N（<=104）是硬币的总个数，M（<=102）是韩梅梅要付的款额。第二行给出N枚硬币的正整数面值。数字间以空格分隔。

输出格式：

在一行中输出硬币的面值 V1 <= V2 <= … <= Vk，满足条件 V1 + V2 + … + Vk = M。数字间以1个空格分隔，行首尾不得有多余空格。若解不唯一，则输出最小序列。若无解，则输出“No Solution”。

注：我们说序列{A[1], A[2], …}比{B[1], B[2], …}“小”，是指存在 k >= 1 使得 A[i]=B[i] 对所有 i < k 成立，并且 A[k] < B[k]。

输入样例1：
8 9
5 9 8 7 2 3 4 1
输出样例1：
1 3 5
输入样例2：
4 8
7 2 4 3
输出样例2：
No Solution

分析：01背包问题，因为要输出从小到大的排列，可以先把硬币面额从大到小排列，然后用bool类型的choice[i][j]数组dp[i][j]是否选取，如果选取了就令choice为true；然后进行01背包问题求解，如果最后求解的结果不是恰好等于所需要的价值的，就输出No Soultion，否则从choice[i][j]判断选取的情况，i从n到1表示从后往前看第i个物品的选取情况，j从m到0表示从容量m到0是否选取(j = j – w[i])，把选取情况压入arr数组中，最后输出arr数组

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int dp[10010];
int w[10010];
bool choice[10010][10010];
int cmp1(int a, int b){return a > b;}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    sort(w + 1, w + n + 1, cmp1);
    for(int i = 1; i <= n; i++) {
        for(int j = m; j >= w[i]; j--) {
            if(dp[j] <= dp[j-w[i]] + w[i]) {
                choice[i][j] = true;
                dp[j] = dp[j-w[i]] + w[i];
            }
        }
    }
    if(dp[m] != m) printf("No Solution");
    else {
        vector<int> arr;
        int v = m, index = n;
        while(v > 0) {
            if(choice[index][v] == true) {
                arr.push_back(w[index]);
                v -= w[index];
            }
            index--;
        }
        for(int i = 0; i < arr.size(); i++) {
            if(i != 0) printf(" ");
            printf("%d", arr[i]);
        }
    }
    return 0;
}

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

int dp[10010];

int w[10010];

bool choice[10010][10010];

int cmp1(int a, int b){return a > b;}

int main() {

int n, m;

scanf("%d%d", &n, &m);

for(int i = 1; i <= n; i++)

scanf("%d", &w[i]);

sort(w + 1, w + n + 1, cmp1);

for(int i = 1; i <= n; i++) {

for(int j = m; j >= w[i]; j--) {

if(dp[j] <= dp[j-w[i]] + w[i]) {

choice[i][j] = true;

dp[j] = dp[j-w[i]] + w[i];

}

if(dp[m] != m) printf("No Solution");

else {

vector<int> arr;

int v = m, index = n;

while(v > 0) {

if(choice[index][v] == true) {

arr.push_back(w[index]);

v -= w[index];

}

index--;

}

for(int i = 0; i < arr.size(); i++) {

if(i != 0) printf(" ");

printf("%d", arr[i]);

}

return 0;

}

【算法】动态规划笔记

将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问题的最优解
动态规划会将每个求解过的子问题的解记录下来，这样下一次碰到同样的子问题时，就可以直接使用之前记录的结果，而不是重复计算
可以用递归或者递推的写法实现，递归的写法又叫记忆化搜索
重叠子问题：如果一个问题可以被分解成若干个子问题，且这些子问题会重复出现，就称这个问题拥有重叠子问题。一个问题必须拥有重叠子问题，才能用动态规划去解决。
最优子结构：如果一个问题的最优解可以由其子问题的最优解有效地构造出来，那么称为这个问题拥有的最优子结构。最优子结构保证了动态规划中的原问题的最优解可以由子问题的最优解推导而来
动态规划与分治的区别：都是分解为子问题然后合并子问题得到解，但是分治分解出的子问题是不重叠的
动态规划与贪心的区别：都有最优子结构，但是贪心直接选择一个子问题去求解，会抛弃一些子问题，这种选择的正确性需要用归纳法证明，而动态规划会考虑所有的子问题

动态规划的递归和递推写法

递归写法

//不使用动态规划
int F(int n) {
  if(n == 0 || n == 1) return 1;
  else return F(n - 1) + F(n - 2);
}
// 此时F(5) = F(4) + F(3), F(4) = F(3) + F(2),3会被计算两次

// 采用动态规划的方法(记忆化搜索)
int dp[10000];
memeset(dp, -1, sizeof(dp));
int F(int n) {
  if(n == 0 || n == 1) return 1;
  if(dp[n] != -1) return dp[n];
  else {
    dp[n] = F(n-1) + F(n - 2);
    return dp[n];
  }
}

//不使用动态规划

int F(int n) {

if(n == 0 || n == 1) return 1;

else return F(n - 1) + F(n - 2);

}

// 此时F(5) = F(4) + F(3), F(4) = F(3) + F(2),3会被计算两次

// 采用动态规划的方法(记忆化搜索)

int dp[10000];

memeset(dp, -1, sizeof(dp));

int F(int n) {

if(n == 0 || n == 1) return 1;

if(dp[n] != -1) return dp[n];

else {

dp[n] = F(n-1) + F(n - 2);

return dp[n];

}

递推写法

// 数塔为例
// 递推方程：f[i][j] += max(f[i+1][j], f[i+1][j+1])
// 如果非要建立dp数组，先要初始化dp[n][j] = f[n][j]   [(j从1~n)]
// 然后dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + f[i][j]
// f[i][j]为第i行j列数字的大小
// 采用自底向上递推的方法
// 数组从1开始作为下标存储
for(int i = n - 1; i >= 1; i--) {
  for(int j = 1; j <= i; j++)
    f[i][j] += max(f[i+1][j], f[i+1][j+1]);
}
return f[1][1];

// 数塔为例

// 递推方程：f[i][j] += max(f[i+1][j], f[i+1][j+1])

// 如果非要建立dp数组，先要初始化dp[n][j] = f[n][j] [(j从1~n)]

// 然后dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + f[i][j]

// f[i][j]为第i行j列数字的大小

// 采用自底向上递推的方法

// 数组从1开始作为下标存储

for(int i = n - 1; i >= 1; i--) {

for(int j = 1; j <= i; j++)

f[i][j] += max(f[i+1][j], f[i+1][j+1]);

}

return f[1][1];

最大连续子序列和

给定序列，求连续的子序列要求和最大，求最大的和为多少
dp[i]表示以a[i]作为末尾的连续序列的最大和（a[i]必须是末尾被选的数啊啊），dp数组中所有的数据的最大值就是所求
dp[0]初始化为a[0]，dp数组从1生成到n-1
因为a[i]一定是所选序列的末尾，所以分为两种情况：
- a[i]开始，a[i]结束
- 某数开始，到a[i]结束（最大和是dp[i-1] + a[i]）
所以递推方程为dp[i] = max(a[i], dp[i-1]+a[i]);
dp数组中所有的数据的最大值就是所求：maxn = max(dp[i], maxn);

// a数组从下标0开始
dp[0] = a[0];
int maxn = a[0];
for(int i = 1; i < n; i++) {
  dp[i] = max(a[i], dp[i-1]+a[i]);
  maxn = max(dp[i], maxn);
}
printf("%d", maxn);

// a数组从下标0开始

dp[0] = a[0];

int maxn = a[0];

for(int i = 1; i < n; i++) {

dp[i] = max(a[i], dp[i-1]+a[i]);

maxn = max(dp[i], maxn);

}

printf("%d", maxn);

最长不下降子序列（LIS）

求一个序列的最长的子序列（可以不连续），使得这个子序列是不下降的
dp[i]表示必须以a[i]结尾的最长不下降子序列的长度，dp数组中所有数据的最大值即为所求
i从0到n-1依次更新dp[i]的值，dp[i]的值需要由之前所生成的所有dp[j]递推而得（j从1到i-1），每次检查是否a[i]>=a[j]，即是否构成最长不下降子序列，如果构成，会有两种结果：
- dp[j]+1比dp[i]大，则更新dp[i] = dp[j] + 1
- dp[j]+1比dp[i]小，则dp[i]保持不变
所以递推方程为dp[i] = max{dp[i], dp[j] + 1};
dp数组中所有数据的最大值即为所求：ans = max(dp[i], ans);

int ans = 0;
for(int i = 0; i < n; i++) {
  for(int j = 1; j < i; j++) {
    if(a[i] >= a[j])
      dp[i] = max(dp[i], dp[j] + 1);
  }
  ans = max(dp[i], ans);
}

printf("%d", ans);

int ans = 0;

for(int i = 0; i < n; i++) {

for(int j = 1; j < i; j++) {

if(a[i] >= a[j])

dp[i] = max(dp[i], dp[j] + 1);

}

ans = max(dp[i], ans);

}

printf("%d", ans);

最长公共子序列（LCS）

给定两个字符串或者数字序列A和B，求一个字符串，使得这个字符串是A和B的最长公共部分（子序列可以不连续）
dp[i][j]表示A的第 i 位之前和B的第 j 位之前的这两个序列的LCS最长公共子序列的长度（下标从1开始），那么dp[lena][lenb]即为所求
递推方程：
- 当a[i] == b[j] : dp[i][j] = dp[i-1][j-1] + 1
- 当a[i] != b[j] : dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- 边界：dp[i][0] = dp[0][j] = 0(0 <= i <= lena, 1 <= j <= lenb)

char a[100], b[100];
scanf("%s", a+1);
scanf("%s", b+1);
int lena = strlen(a + 1), lenb = strlen(b + 1);
for(int i = 0; i <= lena; i++) dp[i][0] = 0;
for(int j = 0; j <= lenb; j++) dp[0][j] = 0;
for(int i = 1; i <= lena; i++) {
  for(int j = 1; j <= lenb; j++) {
    if(a[i] == b[j])
      dp[i][j] = dp[i-1][j-1] + 1;
    else
      dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
  }
}
printf("%d", dp[lena][lenb]);

char a[100], b[100];

scanf("%s", a+1);

scanf("%s", b+1);

int lena = strlen(a + 1), lenb = strlen(b + 1);

for(int i = 0; i <= lena; i++) dp[i][0] = 0;

for(int j = 0; j <= lenb; j++) dp[0][j] = 0;

for(int i = 1; i <= lena; i++) {

for(int j = 1; j <= lenb; j++) {

if(a[i] == b[j])

dp[i][j] = dp[i-1][j-1] + 1;

else

dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

}

printf("%d", dp[lena][lenb]);

最长回文子串

给出一个字符串s，求s的最长回文子串的长度
dp[i][j]表示 s[i] 到 s[j] 所表示的字串是否是回文字串，值只有0和1
初始化长度1和2的值：dp[i][i] = 1, dp[i][i+1] = (s[i] == s[i+1]) ? 1 : 0，然后长度L从3到len，满足的最大长度L即为所求的ans值
递推方程：
- 当s[i] == s[j] : dp[i][j] = dp[i+1][j-1]
- 当s[i] != s[j] : dp[i][j] = 0
因为i、j如果从小到大的顺序来枚举的话，无法保证更新dp[i][j]的时候dp[i+1][j-1]已经被计算过。因此不妨考虑按照字串的长度和子串的初试位置进行枚举，即第一遍将长度为3的子串的dp的值全部求出，第二遍通过第一遍结果计算出长度为4的子串的dp的值…这样就可以避免状态无法转移的问题

int len = s.length();
//先把1和2长度的都初始化了
int ans = 1;
for(int i = 0; i < len; i++) {
  dp[i][i] = 1;
  if(i < len - 1 && s[i] == s[i+1]) {
    dp[i][i+1] = 1;
    ans = 2;
  }
}
//状态转移方程
for(int L = 3; L <= len; L++) {
  for(int i = 0; i + L - 1 < len; i++) {
    int j = i + L - 1;
    if(s[i] == s[j] && dp[i+1][j-1] == 1) {
      dp[i][j] = 1;
      ans = L;
    }
  }
}
printf("%d", ans);

int len = s.length();

//先把1和2长度的都初始化了

int ans = 1;

for(int i = 0; i < len; i++) {

dp[i][i] = 1;

if(i < len - 1 && s[i] == s[i+1]) {

dp[i][i+1] = 1;

ans = 2;

}

//状态转移方程

for(int L = 3; L <= len; L++) {

for(int i = 0; i + L - 1 < len; i++) {

int j = i + L - 1;

if(s[i] == s[j] && dp[i+1][j-1] == 1) {

dp[i][j] = 1;

ans = L;

}

printf("%d", ans);

背包问题

01背包问题

有n件物品，每件物品的重量为w[i]，价值为c[i]。现有一个重量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品只有1件
dp[i][j]表示前i件物品恰好装入容量为j的背包所能获得的最大价值
- 不放第i件物品，则 dp[i][j] = dp[i-1][j]
- 放第i件物品，那么问题转化为前i – 1件物品恰好装入容量j – w[i]的背包中所能获得的最大价值 dp[i-1][j-w[i]] + c[i]
递推方程dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+c[i]);

for(int i = 1; i <= n; i++) {
  for(int j = 1, j <= v; j++)
    if(j - w[i] >= 0) 
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + c[i]);
    else
      dp[i][j] = dp[i-1][j];    
}

for(int i = 1; i <= n; i++) {

for(int j = 1, j <= v; j++)

if(j - w[i] >= 0)

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + c[i]);

else

dp[i][j] = dp[i-1][j];

}

一维：

for(int i = 1; i <= n; i++) {
  for(int j = v; j >= w[i]; j--)
    dp[v] = max(dp[v], dp[v-w[i]] + c[i]);
}

for(int i = 1; i <= n; i++) {

for(int j = v; j >= w[i]; j--)

dp[v] = max(dp[v], dp[v-w[i]] + c[i]);

}

1068. Find More Coins (30)-PAT甲级真题（01背包）

Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she must pay the exact amount. Since she has as many as 104 coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find some coins to pay for it.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive numbers: N (<=104, the total number of coins) and M(<=102, the amount of money Eva has to pay). The second line contains N face values of the coins, which are all positive numbers. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the face values V1 <= V2 <= … <= Vk such that V1 + V2 + … + Vk = M. All the numbers must be separated by a space, and there must be no extra space at the end of the line. If such a solution is not unique, output the smallest sequence. If there is no solution, output “No Solution” instead.

Note: sequence {A[1], A[2], …} is said to be “smaller” than sequence {B[1], B[2], …} if there exists k >= 1 such that A[i]=B[i] for all i < k, and A[k] < B[k].

Sample Input 1:
8 9
5 9 8 7 2 3 4 1
Sample Output 1:
1 3 5
Sample Input 2:
4 8
7 2 4 3
Sample Output 2:
No Solution
题目大意：用n个硬币买价值为m的东西，输出使用方案，使得正好几个硬币加起来价值为m。从小到大排列，输出最小的那个排列方案
分析：01背包问题，因为要输出从小到大的排列，可以先把硬币面额从大到小排列，然后用bool类型的choice[i][j]数组dp[i][j]是否选取，如果选取了就令choice为true；然后进行01背包问题求解，如果最后求解的结果不是恰好等于所需要的价值的，就输出No Soultion，否则从choice[i][j]判断选取的情况，i从n到1表示从后往前看第i个物品的选取情况，j从m到0表示从容量m到0是否选取(j = j – w[i])，把选取情况压入arr数组中，最后输出arr数组

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dp[10010], w[10010];
bool choice[10010][110];
int cmp1(int a, int b){return a > b;}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    sort(w + 1, w + n + 1, cmp1);
    for(int i = 1; i <= n; i++) {
        for(int j = m; j >= w[i]; j--) {
            if(dp[j] <= dp[j-w[i]] + w[i]) {
                choice[i][j] = true;
                dp[j] = dp[j-w[i]] + w[i];
            }
        }
    }
    if(dp[m] != m) printf("No Solution");
    else {
        vector<int> arr;
        int v = m, index = n;
        while(v > 0) {
            if(choice[index][v] == true) {
                arr.push_back(w[index]);
                v -= w[index];
            }
            index--;
        }
        for(int i = 0; i < arr.size(); i++) {
            if(i != 0) printf(" ");
            printf("%d", arr[i]);
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int dp[10010], w[10010];

bool choice[10010][110];

int cmp1(int a, int b){return a > b;}

int main() {

int n, m;

scanf("%d%d", &n, &m);

for(int i = 1; i <= n; i++)

scanf("%d", &w[i]);

sort(w + 1, w + n + 1, cmp1);

for(int i = 1; i <= n; i++) {

for(int j = m; j >= w[i]; j--) {

if(dp[j] <= dp[j-w[i]] + w[i]) {

choice[i][j] = true;

dp[j] = dp[j-w[i]] + w[i];

}

if(dp[m] != m) printf("No Solution");

else {

vector<int> arr;

int v = m, index = n;

while(v > 0) {

if(choice[index][v] == true) {

arr.push_back(w[index]);

v -= w[index];

}

index--;

}

for(int i = 0; i < arr.size(); i++) {

if(i != 0) printf(" ");

printf("%d", arr[i]);

}

return 0;

}

蓝桥杯 ADV-205 算法提高拿糖果（动态规划）

问题描述
妈妈给小B买了N块糖！但是她不允许小B直接吃掉。
　　假设当前有M块糖，小B每次可以拿P块糖，其中P是M的一个不大于根号下M的质因数。这时，妈妈就会在小B拿了P块糖以后再从糖堆里拿走P块糖。然后小B就可以接着拿糖。
　　现在小B希望知道最多可以拿多少糖。
输入格式
　　一个整数N
输出格式
　　最多可以拿多少糖
样例输入
15
样例输出
6
数据规模和约定
N <= 100000

分析：动态规划问题~~首先呢~创建一个满足不大于根号下最大值MAXN的素数表，然后对素数表里面的数逐个遍历~
构建一个dp[i]数组,表示当糖果数量为i的时候所能拿的最多的糖果数量~
对于dp[i]的值：因为小B只能每次拿不大于根号下i的质因数，遍历素数表中满足条件的素数（prime[j] <= sqrt(i) && i % prime[j] == 0），更新dp[i]的值为（dp[i-2*prime[j]] + prime[j]）的最大值~
即：dp[i] = max(dp[i], dp[i-2*prime[j]] + prime[j]);

#include <iostream>
#include <cmath>
using namespace std;
int prime[50000];
int dp[100005];
int book[100005];
int cnt = 0;

void create() {
	int len = sqrt(100005);
    for(int i = 2; i <= len; i++) {
        if(book[i] == 0) {
            prime[cnt++] = i;
            for(int j = i * i; j <= len; j = j + i)
                book[j] = 1;
        }
    }
}

int main() {
    create();
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < cnt; j++) {
            if(prime[j] > sqrt(i))
                break;
            if(i % prime[j] == 0)
                dp[i] = max(dp[i], dp[i-2*prime[j]] + prime[j]);
        }
    }
    cout << dp[n];
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int prime[50000];

int dp[100005];

int book[100005];

int cnt = 0;

void create() {

int len = sqrt(100005);

for(int i = 2; i <= len; i++) {

if(book[i] == 0) {

prime[cnt++] = i;

for(int j = i * i; j <= len; j = j + i)

book[j] = 1;

}

int main() {

create();

int n;

cin >> n;

for(int i = 1; i <= n; i++) {

for(int j = 0; j < cnt; j++) {

if(prime[j] > sqrt(i))

break;

if(i % prime[j] == 0)

dp[i] = max(dp[i], dp[i-2*prime[j]] + prime[j]);

}

cout << dp[n];

return 0;

}

蓝桥杯 ADV-144 算法提高 01背包

问题描述
　　给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.
输入格式
　　输入的第一行包含两个整数n, m，分别表示物品的个数和背包能装重量。
　　以后N行每行两个数Wi和Vi,表示物品的重量和价值
输出格式
　　输出1行，包含一个整数，表示最大价值。
样例输入
3 5
2 3
3 5
4 7
样例输出
8
数据规模和约定
　　1<=N<=200,M<=5000.

分析：dp[i][j]表示前i件物品选择部分装入体积为j的背包后，背包当前的最大价值，
一共有n件物品，那么dp[n][m]就是前n件物品选择部分装入容量为m的背包后，背包内物品的最大价值
1.当当前输入的物品体积大于背包容量，则不装入背包，dp[i][j] = dp[i-1][j];
2.当当前输入的物品体积小于等于背包容量，考虑装或者不装两种状态，取体积最大的那个：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);

#include <iostream>
using namespace std;
int dp[201][5001];
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        int w, v;
        cin >> w >> v;
        for(int j = 1; j <= m; j++) {
            if (j >= w)
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[n][m];
    return 0;
}

#include <iostream>

using namespace std;

int dp[201][5001];

int main() {

int n, m;

cin >> n >> m;

for(int i = 1; i <= n; i++) {

int w, v;

cin >> w >> v;

for(int j = 1; j <= m; j++) {

if (j >= w)

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);

else

dp[i][j] = dp[i-1][j];

}

cout << dp[n][m];

return 0;

}

蓝桥杯 ALGO-31 算法训练开心的金明（01背包，动态规划）

问题描述
　　金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：
“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，
肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
　　设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为 j1，j2，……，jk，则所求的总和为：
　　v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号）
　　请你帮助金明设计一个满足要求的购物单。
输入格式
　　输入文件的第1行，为两个正整数，用一个空格隔开：
　　N m
　　（其中N（<30000）表示总钱数，m（<25）为希望购买物品的个数。）
　　从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数
　　v p
　　（其中v表示该物品的价格(v<=10000)，p表示该物品的重要度(1~5)）
输出格式
　　输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<100000000）。
样例输入
1000 5
800 2
400 5
300 5
400 3
200 2
样例输出
3900
分析：01背包问题。对于每一个输入都有买和不买两种状态。
dp[i][j]表示对于前i件物品选择部分购买限定总价不超过j元后，物品的价格与重要程度乘积的总和的最大值
可得dp[m][n]即是所求的解。
1.当当前输入的物品价格大于允许的最大总价j元，则不买，dp[i][j] = dp[i-1][j];
2.当当前输入的物品体积小于等于允许的最大总价j元，考虑买或者不买两种状态，取物品的价格与重要程度乘积的总和最大的那个：dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + t);

#include <iostream>
using namespace std;
int dp[25][30000];
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        for(int j = 1; j <= n; j++) {
            if(j >= a)
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + a * b);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[m][n];
    return 0;
}

#include <iostream>

using namespace std;

int dp[25][30000];

int main() {

int n, m;

cin >> n >> m;

for(int i = 1; i <= m; i++) {

int a, b;

cin >> a >> b;

for(int j = 1; j <= n; j++) {

if(j >= a)

dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + a * b);

else

dp[i][j] = dp[i-1][j];

}

cout << dp[m][n];

return 0;

}