社区讨论
求优化
灌水区参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性，并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @m64pkvkv
- 此快照首次捕获于
- 2025/01/20 15:12 去年
- 此快照最后确认于
- 2025/11/04 11:13 4 个月前
MLE力
题目：有 n 件货物，它们的重量分别为 W
1
,W
2
,...,W
n
，价值分别为 P
1
,P
2
,...,P
n
有一辆载重为 V 的货车，司机想从这 n 件货物中选取若干件，使得货车 满载（即所载货物重量之和恰好为 V ）而归。求：车上货物的总价值最大为多少？
范围：1≤V≤100000
，1≤n≤100，1≤W≤10000
，1≤P≤1000
CPP#include<bits/stdc++.h>
using namespace std;
int v,n,s[101],w[101],f[101][100001];
int main(){
scanf("%d%d",&v,&n);
for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&s[i]);
for(int i=0;i<=n;i++)
for(int j=1;j<=v;j++) f[i][j]=-1;
f[1][1]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=v;j++)
if(j>=w[i]){
if(f[i-1][j-w[i]]==-1) f[i][j]=f[i-1][j];
else f[i][j]=max(f[i-1][j-w[i]]+s[i],f[i-1][j]);
}
else f[i][j]=f[i-1][j];
}
if(f[n][v]==-1) printf("0");
else printf("%d",f[n][v]);
return 0;
}
回复
共 3 条回复，欢迎继续交流。
正在加载回复...