社区讨论
64分 Why?
P2871[USACO07DEC] Charm Bracelet S参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lw7rlaeb
- 此快照首次捕获于
- 2024/05/15 19:54 2 年前
- 此快照最后确认于
- 2024/05/15 19:57 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
int W[3500],D[3500]; //重量和价值
int n,m;
int dp[3500][3500];
int main(){
memset(dp,-0x3f,sizeof(dp));
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>W[i]>>D[i];
}
for(int i=0;i<=m;i++){ //不选物品时候的结果为0
dp[0][i]=0;
}
for(int i=0;i<=n;i++){ //背包容量为0的结果为0
dp[i][0]=0;
}
for(int i=1;i<=n;i++){ //枚举选中的物品
for(int j=1;j<=m;j++){ //枚举背包的大小
if(j<W[i]){
dp[i][j]=dp[i-1][j];
}else{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-W[i]]+D[i]);
}
}
}
cout<<dp[n][m];
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...