解题思路:
dp
注意事项:
1.优化二维数组至一维,就不需要写if判断了,否则需要像地表最强召唤兽那样写if,否则空间不足时的总价格就不会被计算还是0,导致答案错误
2.数组大小要开足
参考代码:
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #define N 1000 using namespace std; int dp[N + 2], t[N + 2], c[N + 2]; int backPack01(int T, int n) { for (int i = 1; i <= n; i++) for (int j = T; j >= t[i]; j--) dp[j] = max(dp[j], dp[j - t[i]] + c[i]); return dp[T]; } int main(int argc, char** argv) { int T, M; cin >> T >> M; for (int i = 1; i <= M; i++) cin >> t[i] >> c[i]; cout << backPack01(T, M) << endl; return 0; }
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:533 |
C语言程序设计教程(第三版)课后习题12.3 (C语言代码)浏览:836 |
C二级辅导-进制转换 (C语言代码)浏览:615 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:517 |
九宫重排 (C++代码)浏览:2160 |
人见人爱A+B (C语言代码)浏览:628 |
上车人数 (C语言代码)浏览:781 |
输出正反三角形 (C语言代码)浏览:794 |
WU-蓝桥杯算法提高VIP-Quadratic Equation (C++代码)浏览:1754 |
C语言程序设计教程(第三版)课后习题6.5 (C++代码)浏览:458 |