解题思路:
用dp重新写一下,不过不用dp也能过,可能是测试数据比较水
注意事项:
参考代码:
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <string> #include <algorithm> #include <stdio.h> #define N 100 using namespace std; int v[N + 2], w[N + 2];//价格,价值 //int dp[N + 2][30002]; int dp[30002]; //完全背包 //int solve(int m, int n)//物品个数,钱数 //{ // for (int i = 1; i <= m; i++) // { // for (int j = 1; j <= n; j++) // { // if (j < v[i]) // dp[i][j] = dp[i - 1][j]; // else // dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]); // } // } // return dp[m][n]; //} int solve(int m, int n) { for (int i = 1; i <= m; i++) for (int j = n; j >= v[i]; j--) dp[j] = max(dp[j], dp[j - v[i]] + w[i]); return dp[n]; } int main() { int n, m, vv, p; cin >> n >> m;//钱数,物品个数 for (int i = 1; i <= m; i++) { cin >> vv >> p; v[i] = vv; w[i] = p*vv; } cout << solve(m, n) << endl; return 0; }
0.0分
2 人评分
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:640 |
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:614 |
愚蠢的摄影师 (C++代码)浏览:938 |
核桃的数量 (C语言代码)浏览:872 |
众数问题 (C语言代码)浏览:673 |
筛排处理 (C语言代码)浏览:786 |
小O的数字 (C++代码)浏览:763 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:699 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:523 |
C语言程序设计教程(第三版)课后习题8.2 (C++代码)浏览:661 |