Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:对标准算法提出的怀疑

Posted by 1120121860 at 2013-07-17 17:09:59 on Problem 1015
In Reply To:对标准算法提出的怀疑 Posted by:CZDleaf at 2011-07-22 09:52:21
我也认同你的观点。
以下是我的代码。本人水平有限。但是自认为至少正确性没有问题,是按照传统的01背包思路,i表示前i个候选人中进行选择,不过把j,k作为一个整体当做容量
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
bool path[201][21][801]= {0};
int main(int argc, char *argv[])
{
    const int offset=20;
    int n,m,t=1;
    while(scanf("%d%d",&n,&m) && n||m)
    {
        memset(path,0,sizeof(path));
        int DmP[201];
        int DpP[201];
        int dp[21][801];// 801 <- -[400...400[ <- [0...800]
        int sum=0;
        for(int i=1; i<=n; ++i)
        {
            int D,P;
            scanf("%d%d",&P,&D);
            DmP[i]=D-P+offset;
            DpP[i]=D+P;
        }
        memset(dp,-1,sizeof(dp));
        dp[0][0]=0;
        for(int i=1; i<=n; ++i)
        {
            for(int j=m; j>=1; --j)
            {
                for(int k=m*(20+offset); k>=DmP[i]; --k)
                {
                    if(dp[j-1][k-DmP[i]] != -1 && dp[j][k]<dp[j-1][k-DmP[i]]+DpP[i])
                    {
                        dp[j][k]=dp[j-1][k-DmP[i]]+DpP[i];
                        path[i][j][k]=true;
                    }
                }
            }
        }
        int dmp,dpp,d,p;
        for(int i=0; i<=m*offset; ++i)
        {
            if(dp[m][i+m*offset]!=-1 || dp[m][m*offset-i]!=-1)
            {
                dmp=(dp[m][i+m*offset]>dp[m][m*offset-i])?i:-i;
                dpp=max(dp[m][i+m*offset],dp[m][m*offset-i]);
                d=(dpp+dmp)/2;
                p=(dpp-dmp)/2;
                break;
            }
        }

        printf("Jury #%d\nBest jury has value %d for prosecution and value %d for defence:\n",t++,p,d);
        vector<int> ans;
        for(int i=n,j=m,k=dmp+m*offset; i>=1; --i)
        {
            if(path[i][j][k])
            {
                ans.push_back(i);
                --j;
                k-=DmP[i];
            }
        }
        sort(ans.begin(),ans.end());
        for(int i=0;i<ans.size();++i)
        {
            printf(" %d",ans[i]);
        }
        printf("\n");
    }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator