Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 01背包第一次自己做 纪念一下

Posted by GSMU at 2016-03-09 17:31:19 on Problem 3624
```#include <iostream>
#include <string>
#include <vector>
#include <memory.h>
#include <cstdio>
using namespace std;
int w[3410];//重量
int p[3410];//价值
int maxKnow[12880];
int cases;
int value;

int dp(int value)
{
int i ,j;
for(i = 1;i <= cases; i++)
{
for(j = value; j -w[i]>=0 ;j--)
{

if(j < w[i])
maxKnow[j] = maxKnow[j-w[i]];
else
{
maxKnow[j] = max(maxKnow[j],maxKnow[j-w[i]] + p[i]);
}
}
}
int ans;
for(int i = 0 ;i <= value;i++)
ans=max(ans,maxKnow[i]);
return ans;
}

int main()
{

int i ;
int max;
while(scanf("%d %d",&cases,&value)!=EOF)
{
memset(w,0,3410*sizeof(int));
memset(p,0,3410*sizeof(int));
//memset(c,0,3410*12880*sizeof(int));
memset(maxKnow,0,12880*sizeof(int));
for(i = 0;i<cases;i++)
{
scanf("%d %d",&w[i+1],&p[i+1]);
}
max = dp(value);
cout << max << endl;
}
}
```

Followed by: