ACM题-杭电OJ2602
参考

Problem Description

Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …

The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?

Input

The first line contain a integer T , the number of cases.
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.

Output

One integer per line representing the maximum of the total value (this number will be less than 2^31).

Sample Input

1
5 10
1 2 3 4 5
5 4 3 2 1

Sample Output

14

AC代码

/**
 *    author:  admin
 *    created: 05.29.05 17:15:14
**/
# include <bits/stdc++.h>

using namespace std;
const int N = 1e3 + 5, V = 1e3 + 5;
int dp[N][N];
int value[N], volume[N];

int main() {
# ifdef ONLINE_JUDGE
# else
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
# endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T, n, v;
    cin >> T;//T组数据
    while (T--) {
        memset(dp, 0, sizeof(dp));//格式化整个dp数组，每个元素为0
        cin >> n >> v;//n个bone，总体积为v
        for (int i = 1; i <= n; ++i) {
            cin >> value[i];
        }
        for (int i = 1; i <= n; ++i) {
            cin >> volume[i];
        }
        for (int i = 1; i <= n; ++i) {//从第1件物品到第n件物品依次进行选择
            for (int j = 0; j <= v; ++j) {//从0到v容量比较
                if (volume[i] <= j) {//如果第i件物品的容量小于等于j
                    dp[i][j] = max(dp[i - 1][j],
                                   dp[i - 1][j - volume[i]] + value[i]);//比较不拿第i件物品和拿第i件物品，谁更优
                } else {
                    dp[i][j] = dp[i - 1][j];//第i件物品容量大于j，拿不了，在j容量下从第1件选到第i件物品最优解是dp[i-1][j]
                }
            }
        }
        cout << dp[n][v] << endl;//每个局部最优到整体最优
//        for (int l = 0; l <=n; ++l) {//打印比较拿或不拿过程
//            for (int i = 0; i <=v ; ++i) {
//                cerr<<dp[l][i]<<"\t";
//            }
//            cerr<<endl;
//        }
    }
    return 0;
}

例子：
5 10
1 2 3 4 5
5 4 3 2 1
二维数组

容量        0   1   2   3   4   5   6   7   8   9   10
            0   0   0   0   0   0   0   0   0   0   0   
选择第1个物品 0   0   0   0   0   1   1   1   1   1   1   
选择第2个物品 0   0   0   0   2   2   2   2   2   3   3   
选择第3个物品 0   0   0   3   3   3   3   5   5   5   5   
选择第4个物品 0   0   4   4   4   7   7   7   7   9   9   
选择第5个物品 0   5   5   9   9   9   12  12  12  12  14

每个物品在选择时，只有两种情况，拿或者不拿，所以称01两种状态背包
dp[i][j]表示第1～i个物品在j容量下的最优解

        for (int i = 1; i <= n; ++i) {//从第1件物品到第n件物品依次进行选择
            for (int j = 0; j <= v; ++j) {//从0到v容量比较
                if (volume[i] <= j) {//如果第i件物品的容量小于等于j
                    dp[i][j] = max(dp[i - 1][j],
                                   dp[i - 1][j - volume[i]] + value[i]);//比较不拿第i件物品和拿第i件物品，谁更优
                } else {
                    dp[i][j] = dp[i - 1][j];//第i件物品容量大于j，拿不了，在j容量下从第1件选到第i件物品最优解是dp[i-1][j]
                }
            }
        }