c/c++[002]:01背包

发表于 更新于 分类于

(背包问题?)[https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/3092.html] 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
    //std::ios::sync_with_stdio(false);
    int n;
    int sum ;
    int w[2][20000];
    int sV[20000];
    int i = 0;
    while (cin >> n >> sum)
    {
        i = 1;
        while(i <= n)
        {
            cin>>w[0][i] >> w[1][i];
            i++;
        }
        memset(sV,0,sizeof(sV));
        for(int j = 0; j<= n ; j++)
        {
            for( int jj = sum ; jj >= w[0][j]; jj -- )
            {
                sV[jj] = max(
                         sV[jj],
                         sV[jj-w[0][j]]+w[1][j]
                         );
            }
//            for(int z = 0; z<=sum ;z++){
  //              cout<<sV[z]<<"\t";
    //        }
      //      cout<<endl;
        }
        cout<< sV[sum]<<endl;

    }

    return 0 ;
}