目录
题目详情题面分析代码
题目详情
题面传送门
题面分析
从
v
[
j
1
]
×
w
[
j
1
]
+
v
[
j
2
]
×
w
[
j
2
]
+
…
+
v
[
j
k
]
×
w
[
j
k
]
v[j~1~]×w[j~1~]+v[j~2~]×w[j~2~]+…+v[j~k~]×w[j~k~]
v[j 1 ]×w[j 1 ]+v[j 2 ]×w[j 2 ]+…+v[j k ]×w[j k ]中就可以立刻地看出： 他是个背包板子题 总体就是个背包
d
p
dp
dp。 没有必要再说了，看代码注释。
代码
#include <bits/stdc++.h>
using namespace std
;
int w
[30],v
[30],f
[50000];
int n
,m
;
int main(){
cin
>>m
>>n
;
for(int i
=1;i
<=n
;i
++){
cin
>>v
[i
]>>w
[i
];
w
[i
]*=v
[i
];
}
for(int i
=1;i
<=n
;i
++)
for(int j
=m
;j
>=v
[i
];j
--)
if(j
>=v
[i
]) f
[j
]=max(f
[j
],f
[j
-v
[i
]]+w
[i
]);
cout
<<f
[m
]<<endl
;
return 0;
}
