Cloud_Ivy37 @ 2024-09-10 21:50:02
80分的代码 WA: #8 #9 #11
//动态规划-01背包-二维
#include<iostream>
#include<vector>
using namespace std;
const int N=2e4+5;
int n,m;
vector<pair<int,int>>item[N];
int dp[N][N];
//dp[i][j]:在前i个物品中选,并且金额为j的价值的集合
//性质:max
/*
状态计算:
1 不选
2 只选主件
3 选主件并且选附件1
4 选主件并且选附件2
5 选主件并且选附件1和附件2
*/
void input(){
cin>>m>>n;
for(int i=1;i<=n;i++){
int price,value,flag;
cin>>price>>value>>flag;
if(!flag) item[i].push_back({price,value*price});
else item[flag].push_back({price,value*price});
}
}
int main(){
input();
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
dp[i][j]=dp[i-1][j];
if(item[i].size()==1)
if(j>=item[i][0].first)
dp[i][j]=max(dp[i][j],dp[i-1][j-item[i][0].first]+item[i][0].second);
if(item[i].size()==2){
if(j>=item[i][0].first)
dp[i][j]=max(dp[i][j],dp[i-1][j-item[i][0].first]+item[i][0].second);
if(j>=item[i][0].first+item[i][1].first)
dp[i][j]=max(dp[i][j],dp[i-1][j-item[i][0].first-item[i][1].first]+item[i][0].second+item[i][1].second);
}
if(item[i].size()==3){
if(j>=item[i][0].first)
dp[i][j]=max(dp[i][j],dp[i-1][j-item[i][0].first]+item[i][0].second);
if(j>=item[i][0].first+item[i][1].first)
dp[i][j]=max(dp[i][j],dp[i-1][j-item[i][0].first-item[i][1].first]+item[i][0].second+item[i][1].second);
if(j>=item[i][0].first+item[i][2].first)
dp[i][j]=max(dp[i][j],dp[i-1][j-item[i][0].first-item[i][2].first]+item[i][0].second+item[i][2].second);
if(j>=item[i][0].first+item[i][1].first+item[i][2].first)
dp[i][j]=max(dp[i][j],dp[i-1][j-item[i][0].first-item[i][1].first-item[i][2].first]+item[i][0].second+item[i][1].second+item[i][2].second);
}
}
}
cout<<dp[n][m]<<endl;
return 0;
}优化成一维 WA:#11
//动态规划-01背包-一维
#include<iostream>
#include<vector>
using namespace std;
const int N=32005,M=200005;
int n,m;
vector<pair<int,int>>item[N];
int dp[M];
//dp[j]:在前n个物品中选,并且金额为j的价值的集合
//性质:max
/*
状态计算:
1 不选
2 只选主件
3 选主件并且选附件1
4 选主件并且选附件2
5 选主件并且选附件1和附件2
*/
void input(){
cin>>m>>n;
for(int i=1;i<=n;i++){
int price,value,flag;
cin>>price>>value>>flag;
if(!flag) item[i].push_back({price,value*price});
else item[flag].push_back({price,value*price});
}
}
int main(){
input();
for(int i=1;i<=n;i++){
for(int j=m;j>=0;j--){
if(item[i].size()==1)
if(j>=item[i][0].first)
dp[j]=max(dp[j],dp[j-item[i][0].first]+item[i][0].second);
if(item[i].size()==2){
if(j>=item[i][0].first)
dp[j]=max(dp[j],dp[j-item[i][0].first]+item[i][0].second);
if(j>=item[i][0].first+item[i][1].first)
dp[j]=max(dp[j],dp[j-item[i][0].first-item[i][1].first]+item[i][0].second+item[i][1].second);
}
if(item[i].size()==3){
if(j>=item[i][0].first)
dp[j]=max(dp[j],dp[j-item[i][0].first]+item[i][0].second);
if(j>=item[i][0].first+item[i][1].first)
dp[j]=max(dp[j],dp[j-item[i][0].first-item[i][1].first]+item[i][0].second+item[i][1].second);
if(j>=item[i][0].first+item[i][2].first)
dp[j]=max(dp[j],dp[j-item[i][0].first-item[i][2].first]+item[i][0].second+item[i][2].second);
if(j>=item[i][0].first+item[i][1].first+item[i][2].first)
dp[j]=max(dp[j],dp[j-item[i][0].first-item[i][1].first-item[i][2].first]+item[i][0].second+item[i][1].second+item[i][2].second);
}
}
}
cout<<dp[m]<<endl;
return 0;
}发现HACK数据为:
输入：
100 3
1000 5 3
10 5 3
50 2 0
输出：
150重新改一下输入即可AC:
void input(){
cin>>m>>n;
for(int i=1;i<=n;i++) cin>>node[i].p>>node[i].v>>node[i].f;
for(int i=1;i<=n;i++){
int price=node[i].p,value=node[i].v,flag=node[i].f;
if(!flag) item[i].push_back({price,value*price});
}
for(int i=1;i<=n;i++){
int price=node[i].p,value=node[i].v,flag=node[i].f;
if(flag) item[flag].push_back({price,value*price});
}
}完整AC_code:
//动态规划-01背包-一维
#include<iostream>
#include<vector>
using namespace std;
const int N=32005,M=200005;
int n,m;
struct NODE{
int p,v,f;
}node[N];
bool cmp(NODE a,NODE b){
return a.f<=b.f;
}
vector<pair<int,int>>item[N];
int dp[M];
//dp[j]:在前n个物品中选,并且金额为j的价值的集合
//性质:max
/*
状态计算:
1 不选
2 只选主件
3 选主件并且选附件1
4 选主件并且选附件2
5 选主件并且选附件1和附件2
*/
void input(){
cin>>m>>n;
for(int i=1;i<=n;i++) cin>>node[i].p>>node[i].v>>node[i].f;
for(int i=1;i<=n;i++){
int price=node[i].p,value=node[i].v,flag=node[i].f;
if(!flag) item[i].push_back({price,value*price});
}
for(int i=1;i<=n;i++){
int price=node[i].p,value=node[i].v,flag=node[i].f;
if(flag) item[flag].push_back({price,value*price});
}
}
int main(){
input();
for(int i=1;i<=n;i++){
for(int j=m;j>=0;j--){
if(item[i].size()==1)
if(j>=item[i][0].first)
dp[j]=max(dp[j],dp[j-item[i][0].first]+item[i][0].second);
if(item[i].size()==2){
if(j>=item[i][0].first)
dp[j]=max(dp[j],dp[j-item[i][0].first]+item[i][0].second);
if(j>=item[i][0].first+item[i][1].first)
dp[j]=max(dp[j],dp[j-item[i][0].first-item[i][1].first]+item[i][0].second+item[i][1].second);
}
if(item[i].size()==3){
if(j>=item[i][0].first)
dp[j]=max(dp[j],dp[j-item[i][0].first]+item[i][0].second);
if(j>=item[i][0].first+item[i][1].first)
dp[j]=max(dp[j],dp[j-item[i][0].first-item[i][1].first]+item[i][0].second+item[i][1].second);
if(j>=item[i][0].first+item[i][2].first)
dp[j]=max(dp[j],dp[j-item[i][0].first-item[i][2].first]+item[i][0].second+item[i][2].second);
if(j>=item[i][0].first+item[i][1].first+item[i][2].first)
dp[j]=max(dp[j],dp[j-item[i][0].first-item[i][1].first-item[i][2].first]+item[i][0].second+item[i][1].second+item[i][2].second);
}
}
}
cout<<dp[m]<<endl;
return 0;
}