01背包


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

const int N=1010;
int v[N],w[N],dp[N][N];
int n, m;

int main()
{
  scanf("%d%d",&n,&m);//n是物品数量,m是背包容量

  for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);

  for(int i=1;i<=n;i++) {
    for(int j=1;j<=m;j++)
    {
        if(v[i] > j)
        {
            dp[i][j] = dp[i - 1][j];
        } else
        {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
  }
  printf("%d",dp[n][m]);
  return 0;
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容