解题思路:转化为完全背包, 当数量不限时,数量为背包容量除以物品体积
注意事项:滚动数组优化, j 从m 到 w[i]
参考代码:
#include<iostream> #include<algorithm> using namespace std; const int N = 2e2 + 10; int f[N],w[N],c[N],p[N]; int main() { int n, m; cin >> m >> n; for(int i = 1; i <= n; i ++){ cin >> w[i] >> c[i] >> p[i]; if (!p[i]) p[i] = m / w[i]; } for(int i = 1; i <= n; i ++) for(int j = m; j >= w[i]; j --) for(int k = 0; k <= p[i]; k ++) if(j >= k * w[i]) f[j] = max(f[j],f[j - k * w[i]] + k * c[i]); cout <<f[m]; return 0; }
0.0分
1 人评分
回文数字 (C语言代码)浏览:2510 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:558 |
整除问题 (C语言代码)浏览:526 |
生日日数 (C语言代码)浏览:1502 |
A+B for Input-Output Practice (III) (C语言代码)浏览:424 |
C语言程序设计教程(第三版)课后习题10.1 (C++代码)浏览:503 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:692 |
求圆的面积 (C语言代码)浏览:657 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:527 |
蓝桥杯基础练习VIP-报时助手 (C++代码)浏览:1066 |