WA:#8 #9 #11 的过来
查看原帖
WA:#8 #9 #11 的过来
1091709
Cloud_Ivy37楼主2024/9/10 21:50

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;
}
2024/9/10 21:50