C++ 解法, 执行用时: 3ms, 内存消耗: 440KB, 提交时间: 2021-12-22

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, V;
    int maxW = 0;
    cin>>n>>V;
    vector<int> dp(V+1, 0);
    int vi, wi;
    for (int i=0;i<n;i++) {
        cin>>vi>>wi;
        if(vi<=V) {
            dp[vi] = max(dp[vi], wi);
        }
    }
 
    for(int i=0;i<=V;i++) {
        for(int j=1;j<=i/2;j++) {
            if(dp[j]&&dp[i-j]) {
                dp[i] = max(dp[i], dp[j]+dp[i-j]);
            }  
        }
        maxW = max(maxW, dp[i]);
    }
    cout<<maxW<<endl;
    cout<<dp[V]<<endl;
    return 0;
}

C 解法, 执行用时: 4ms, 内存消耗: 340KB, 提交时间: 2022-05-08

#include<stdio.h>
int getmax(int a,int b){
    return a > b ? a : b;
}
int main(){
    int V,n;
    int i,j;
    scanf("%d",&n);
    scanf("%d",&V);
    int* value = (int*)malloc(n*sizeof(int));
    int* weight = (int*)malloc(n*sizeof(int));
    for(i = 0; i < n;i++){
        scanf("%d %d",&weight[i],&value[i]);       
    }
    int* dp1 = (int*)calloc(V + 1,sizeof(int));
    int* dp2 = (int*)calloc(V + 1,sizeof(int));
    for(j = 1; j <= V;j++){ 
        dp2[j] = -100000000;
    } 
    for(j = 1; j <= V;j++){
        for(i = 0; i < n; i++){
            if(j >= weight[i]){
                dp1[j] = getmax(dp1[j], dp1[ j - weight[i] ] + value[i]); 
                dp2[j] = getmax(dp2[j], dp2[ j - weight[i] ] + value[i]); 
//                 printf("%d %d \n",j ,dp2[j]);
            }  
        }              
    }
    printf("%d\n%d",dp1[V],getmax(0,dp2[V]));
    return 0;
}

C 解法, 执行用时: 4ms, 内存消耗: 352KB, 提交时间: 2022-03-08

#include<stdio.h>
#include<string.h>
int max(int a,int b)
{
    return a>b?a:b;
}
const int maxn=1e3+5;
int main()
{
    int n,V;
    int v[maxn],w[maxn];
    scanf("%d%d\n",&n,&V);
    int dp[maxn];
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i],&w[i]);
    }
    memset(dp,-1,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=V-v[i];j++)
        {
            if(dp[j]>=0)
            {
                dp[j+v[i]]=max(dp[j+v[i]],dp[j]+w[i]);
            }
        }
    }
    int mx=0;
    for(int i=0;i<=V;i++)
    {
        mx=max(mx,dp[i]);
    }
    //printf("%d",mx);
    if(dp[V]==-1)
    {
        dp[V]=0;
    }
    printf("%d\n%d\n",mx,dp[V]);
    return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 400KB, 提交时间: 2021-11-18

#include <iostream>
using namespace std;
int main(){
    int n,V;
    int v,w,d[1001]{0};
    //scanf("%d%d",&n,&V);
    cin>>n>>V;
    for(int i=0;i<n;i++){
        //scanf("%d%d",&v,&w);
        cin>>v>>w;
        for(int j=0;j<=V-v;j++){
            if(d[j]!=0 || j==0){
//                 int ip=(V-j)/v;
//                 for(int k=1;k<=ip;k++){
//                     d[j+k*v]=max(d[j+k*v],d[j]+k*w);
//                 }
                d[j+v]=max(d[j+v],d[j]+w);
            }
        }
    }
    w=0;
    for(int ii=1;ii<=V;ii++){
        if(d[ii]>w)
            w=d[ii];
        //w=max(w, d[ii]);
    }
    cout<<w<<endl<<d[V]<<endl;
    //printf("%d\n%d\n",maxw,d[V]);
}

C++ 解法, 执行用时: 4ms, 内存消耗: 412KB, 提交时间: 2022-05-14

#include <algorithm>
#include <cstdio>
using namespace std;

const int MAX_N = 1001;
const int MIN_INF = 1 << 31;
int n, V;
int dp[MAX_N], dp2[MAX_N];
int v[MAX_N], w[MAX_N];

int main() {
    scanf("%d %d", &n, &V);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &v[i], &w[i]);
    }

    fill(dp + 1, dp + V + 1, MIN_INF);
    for (int i = 1; i <= n; i++) {
        for (int j =  v[i - 1]; j <= V; j++) {
            dp[j] = max(dp[j], dp[j - v[i - 1]] + w[i - 1]);
            dp2[j] = max(dp2[j], dp2[j - v[i - 1]] + w[i - 1]);
        }
    }

   
    
    printf("%d\n%d", dp2[V], max(0, dp[V]));

    return 0;
}