我错哪了
2023-02-15 17:21:20
发布于:广东
39阅读
0回复
0点赞
洛谷里这个没有re的
#include<bits/stdc++.h>
using namespace std;
int dp[21000][21000]={},mx=0,c,n;
struct t{
int v,w;
}th[1010];
int main(){
cin>>c>>n;
for(int i=1;i<=n;i++){
cin>>th[i].w;
th[i].v=th[i].w;
}
for(int i=1;i<=c;i++){
for(int j=1;j<=n;j++){
if(i>=th[j].w){
dp[i][j]=max(dp[i][j-1],dp[i-th[j].w][j-1]+th[j].v);
}
else{
dp[i][j]=dp[i][j-1];
}
}
}
// for(int i=1;i<=c;i++){
// for(int j=1;j<=n;j++){
// cout<<dp[i][j]<<" ";
// }
// cout<<endl;
// }
cout<<c-dp[c][n];
}
全部评论 2
dp的模板理解之后就直接套了,不必弄那么复杂吧
2023-08-22 来自 安徽
0可设一个元素个数为 max(v)+1的数组dp[20001],里面任意一个元素dp[i]表示箱子容积为 i 时可放入的物品的体积。因为物品的体积并不是单位体积,因此dp[i]并不一定等于 i,例如有3个物体,体积分别为3,4,5,那么容积为3和4的箱子可放入的物品的体积均为3,即dp[3] = dp[4] = 3。对于每一个物体,都有两种选择-放入或者不放入,所以外层循环可对每个物品进行
2023-03-17 来自 上海
0
有帮助,赞一个