C 解法, 执行用时: 3ms, 内存消耗: 340KB, 提交时间: 2022-07-23

#include "stdio.h"
#include "stdlib.h"

int max(int a,int b)
{
    return a>b?a:b;
}

int main()
{
  int n,V;
  scanf("%d%d",&n,&V);
    
  int *vi=(int*)malloc(sizeof(int)*n);
  int *wi=(int*)malloc(sizeof(int)*n);
    
   for(int i=0;i<n;i++)
   { 
       scanf("%d %d",&vi[i],&wi[i]);
   }
    
  int *dp=(int*)malloc(sizeof(int)*(V+1));
  dp[0]=0 ; 

  for(int i=1;i<V+1;i++)
      dp[i]=0x80000000;
    
  int max_dp=0;
  int j;
    
  for(int i=1;i<=n;i++)
  {
      for(j=V;j>=vi[i-1];j--)
      {
          dp[j]=max(dp[j-vi[i-1]]+wi[i-1],dp[j]);
          if(dp[j]>max_dp)
            max_dp=dp[j];
      }    
  }  
  printf("%d\n",max_dp);  
  max_dp=dp[V];
 free(dp);
  if(max_dp<0)
    printf("0");
  else
    printf("%d",max_dp);       
}

C 解法, 执行用时: 3ms, 内存消耗: 356KB, 提交时间: 2021-11-30

#include <stdio.h>
#include <stdlib.h>
#define N 4000
#include "string.h"
#define INF 0x80000000
int max(int a,int b){
int i=a>b? a:b;
return i;	
}

int main()
{
	int n,V,a[N],dp[N],b[N],j,i;
	scanf("%d%d",&n,&V);
	for(i=0;i<n;i++)
	{
		scanf("%d %d",&a[i],&b[i]);
		dp[i]=0; 
	}
	
	for(i=1;i<=n;i++)
	{
		for(j=V;j>=a[i-1];j--){
			dp[j]=max(dp[j-a[i-1]]+b[i-1],dp[j]);
		}
	}
	printf("%d\n",dp[V]);
	for(i=1;i<=V;i++)
	{
		dp[i]=INF;
	}
	
	for(i=1;i<=n;i++)
	{
		for(j=V;j>=a[i-1];j--){
		dp[j]=max(dp[j-a[i-1]]+b[i-1],dp[j]);
		}
	}
	if(dp[V]>0)
	printf("%d",dp[V]);
	else printf("0");
	
}

C 解法, 执行用时: 3ms, 内存消耗: 384KB, 提交时间: 2022-03-11

int max(int a, int b) {
    return a > b ? a : b;
}

int main(void) {
    int n, V;
    scanf("%d %d", &n, &V);
    int *v = malloc(sizeof(int) * n);
    int *m = malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &v[i], &m[i]);
    }
    
    int *dp = malloc(sizeof(int) * (V+1));
    memset(dp, -0x3f, sizeof(int) * (V + 1));
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = V; j >= v[i]; j--) {
            dp[j] = max(dp[j - v[i]] + m[i], dp[j]);
        }
    }
    
    int ans = 0;
    for (int i = 0; i <= V; i++) {
        ans = max(ans, dp[i]);
    }
    printf("%d\n", ans);
    if (dp[V] < 0) {
        printf("0\n");
    } else {
        printf("%d\n", dp[V]);
    }
    free(dp);
    free(m);
    free(v);
    return 0;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 420KB, 提交时间: 2021-10-21

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1010;
const int INF = 0x3f3f3f3f;

int n, V, v[N], w[N], dp[N];

int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> V;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i] >> w[i];
    }

    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++)
        for (int j = V; j >= v[i]; j--)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

    cout << dp[V] << endl;

    memset(dp, -0x3f, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = V; j >= v[i]; j--)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

    if (dp[V] < 0) dp[V] = 0;
    cout << dp[V] << endl;
    return 0;
}

C 解法, 执行用时: 3ms, 内存消耗: 432KB, 提交时间: 2021-11-21

#include <stdio.h>

int main()
{
    int n,v;
    scanf("%d %d",&n,&v);
    int *volum=(int*)malloc(sizeof(int)*(n+1));
    int *value=(int*)malloc(sizeof(int)*(n+1));
    
    int *bag=(int*)malloc(sizeof(int)*(v+1));
    memset(bag,0,sizeof(int)*(v+1));
    int *cbag=(int*)malloc(sizeof(int)*(v+1));
    memset(cbag,-9999,sizeof(int)*(v+1));
    cbag[0]=0;
    for(int i=1;i<=n;++i)
    {
        scanf("%d %d",volum+i,value+i);
    }
    
    for(int i=1;i<=n;++i)
    {
        for(int j=v;j>=volum[i];--j)
        {
            bag[j]=bag[j]>(bag[j-volum[i]]+value[i])?bag[j]:(bag[j-volum[i]]+value[i]);
            cbag[j]=cbag[j]>(cbag[j-volum[i]]+value[i])?cbag[j]:(cbag[j-volum[i]]+value[i]);
        }
    }
    printf("%d\n",bag[v]);
    printf("%d",cbag[v]<0?0:cbag[v]);
    return 0;
}