#include <bits/stdc++.h>
#define MAX_N 100
#define MAX_V 100
#define INF 100000000
using namespace std;
int n, W;
int w[MAX_N+1];
int v[MAX_V+1];
int dp[MAX_N+1][MAX_N*MAX_V+1];
int main()
{
scanf("%d%d", &n, &W );
for( int i=0; i<n; i++ )
scanf("%d%d", &w[i], &v[i] );
fill( dp[0], dp[0]+MAX_N*MAX_V+1, INF ); // fill 按单元赋值,区别去memset
dp[0][0] = 0;
for( int i=0; i<n; i++ )
for( int j=0; j<= MAX_N*MAX_V; j++) // j小于等于最大价值上限
{
if( j<v[i] )
dp[i+1][j] = dp[i][j];
else
dp[i+1][j] = min( dp[i][j], dp[i][j-v[i]] + w[i] );
}
int res = 0;
//找到最大价值, i就是价值,dp[n][i]为对应价值的最小重量
for( int i=0; i<=MAX_N*MAX_V; i++ )
if( dp[n][i] <= W )
res = i;
printf("%d\n", res );
return 0;
}
法二
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main()
{
int n,w,wi[105],vi[105],dp[10005];
while( scanf("%d %d",&n,&w)!=EOF )
{
int sum=0;
memset(dp,100,sizeof(dp));
dp[0]=0;
for(int i=0; i<n; i++)
scanf("%d %d",&wi[i],&vi[i]),sum+=vi[i]; // sum保存总价值
for(int i=0; i<n; i++)
{
for(int j=sum; j>=vi[i]; j--)
dp[j] = min(dp[j],dp[j-vi[i]]+wi[i]);
}
for(int j=sum;j>=0;j--) // j就是价值
if(dp[j]<=w) // 小于最大重量
{
printf("%d\n",j);
break;
}
}
return 0;
}