【模板】01背包

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

#include "stdio.h"
#include "stdlib.h"
// 抄榜一大佬的
int max(int a,int b)
{
    return a>b?a:b;
}

int main()
{
  int n,V; // 输入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]);
   }
  // dp内存
  int *dp=(int*)malloc(sizeof(int)*(V+1));
  dp[0]=0 ; // 小细节，这里不设置为0. 无法计算出正确答案

  for(int i=1;i<V+1;i++)
      dp[i]=0x80000000; // -2147483648
    
  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);       
}