解题思路:转化为完全背包, 当数量不限时,数量为背包容量除以物品体积
注意事项:滚动数组优化, 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 人评分
A+B for Input-Output Practice (C++代码)浏览:822 |
C二级辅导-等差数列 (C语言代码)浏览:591 |
【蟠桃记】 (C语言代码)浏览:651 |
c primer plus 第十二章 12.1小节浏览:377 |
这可能是一个假的冒泡法浏览:986 |
字符串问题 (C语言代码)浏览:1518 |
P1001 (C语言代码)浏览:801 |
2006年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:471 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:565 |
【计算直线的交点数】 (C语言代码)浏览:1450 |