0-1 背包问题（动态规划）_第一行输入物品的个数n和背包容量c。 第二行输入每个物品的价值v[i]. 第三行输入

题目描述

给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，问如何选择装入背包的物品，使得装入背包的物品的总价值最大？

在选择装入背包的物品时，对每种物品i只能有两种选择，装入或者不装入，不能装入多次，也不能部分装入。
输入

第一行输入物品的个数n。

第二行输入物品的重量序列w。(中间有空格）

第三行输入物品的价值序列v。（中间有空格）

第四行输入背包容量c。

输出

第一行输出装入背包的物品。（用0和1表示，中间无空格）

第二行输出最大价值。
样例输入

3
3 4 5
4 5 6
10

4
2 1 3 2
3 2 4 2
5
1
2
3
4
5
6
7
8
9

样例输出

011
11

1010
7
1
2
3
4
5

CODE:

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

int main()
{
    int n;
    while(cin>>n)
    {
        int i,c,j,t;
        int w[1000],v[1000],f[100][100],b[1000];
        for(i=1; i<=n; i++)
            cin>>w[i];
        for(i=1; i<=n; i++)
            cin>>v[i];
        cin>>c;
        memset(f,0,sizeof(f));
        for(i=1; i<=n; i++)
        {
            for(j=c; j>=w[i]; j--)
            {
                f[i][j]=max(f[i-1][j-w[i]]+v[i],f[i-1][j]);
            }
        }
        t=f[n][c];
        for(i=n;i>=1;i--)
        {
            if(f[i][c]>f[i-1][c])
            {
                b[i]=1;
                c=c-w[i];
            }
            else
                b[i]=0;
        }
        for(i=1; i<=n; i++)
            cout<<b[i];
        cout<<endl<<t<<endl;
    }

    return 0;
}

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
42
43
44