问题描述

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 231).

Sample Input
1
5 10
1 2 3 4 5
5 4 3 2 1

Sample Output
14

源码

#include<iostream>
#include<stdio.h>
#include<string.h>
#define max(a, b) a > b ? a : b
using namespace std;
int dp[1005][1005];
// 物品数量 背包容量
// 物品价值
// 物品体积
int fun(int N, int W, int w[1000], int v[1000]) {
    int i, j;
    memset(dp, 0, sizeof(dp));

    for (j = 0; j <= W; j++) dp[0][j] = 0;
    //按以下方案填充数组，是一行一行的填充， 每一行填充完毕，才填充接下来的一行
    //翻译： 分别解决 前 1 个物品在， 0 ~ w下所能构成的最优装载方案
    //      前 2 个物品在 0 ~  w下最优填充方案
    //      但是可以理解为， 仅仅是对第二个物品的讨论， 只有放入与不放入， 并且分别讨论 容量为 0 ~ w 下个情况
    //      总结一句话， 分别讨论在 0 ~ w 总共 w 种情况下，第 2 个物品是否放入

    //      接下来讨论第 3 个 物品是否放入， 
    /*      要明白某一组确定的 i， j下 ，  dp[i][j] 的意思为， 前i个物品放入容量为j的背包的最大价值， 要始终名明确，
            i,j 的值不能改变， 相当于一个子问题*/
    //      自然地，若第三个物瓶确定不放入， 则  dp[i][j]    =    dp[i - 1][j]   注意j 的值不变‘
    //      若第三确定放入                则  dp[i][j]    =    dp[i - 1][j - w[i]] + v[i]
    //                                     ↑ 欲求原问题       ↑依赖于子问题
    for (i = 1; i <= N; i++)
    {
        for (j = 0; j <= W; j++)
        {
            if (j < w[i]) dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
        }
    }

    return dp[N][W];
}

int main() {
    int t;
    int N, W;

    cin >> t;
    while (t--) {
        int w[1000] = { 0 }, v[1000] = { 0 };
        int i;
        cin >> N;
        cin >> W;

        for (i = 1; i <= N; i++)
            cin >> v[i];

        for (i = 1; i <= N; i++)
            cin >> w[i];


       cout << fun(N, W, w, v) << endl;

    }
    //  system("pause");
    return 0;
}

一些感悟

大数组要开在全局区 数组的大小要严格按照题目的说明 对于多组数据的测试，每柱开始测试前所有数据都要初始化，很重要，有时候很可能单组数据可以过，多组就不行 对于循环的计数的起点要有一定的选择