小P寻宝记——好基友一起走（完全背包）

太过爱你忘了你带给我的痛 2022-07-12 04:29 122阅读 0赞

[sdut原题链接][sdut]

小P寻宝记——好基友一起走  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
话说，上次小P到伊利哇呀国旅行得到了一批宝藏。他是相当开心啊，回来就告诉了他的好基友小鑫，于是他们又结伴去伊利哇呀国寻宝。  
这次小P的寻宝之路可没有那么的轻松，他们走到了一个森林，小鑫一不小心被触发了机关，被困在了一个大笼子里面，笼子旁边上有一道题目和一个密码锁，上面说只要解出此题输入密码即可救出被困人。小鑫不是很聪明，所以他做不出来，他知道小P很笨，更解不出来。所以他就让小P独自回去，不用管他。但是小P重情重义不会抛弃他离去。他说：“不，好基友一起走！”。于是就感动了上帝，上帝特派你来替他们解决问题。聪明的你要加油了啊！  
题目描述：给你n种物品和一个体积为v的包包。每种物品有无数种，体积是vi价值是wi。求出包包v所能装的最大价值的东西。

Input  
多组输入。第一行有两个正整数n(0

#include <stdio.h>
    #include <string.h>
    #define Max(a, b) (a > b? a: b)
    int main()
    {
        int n, v, i, j;
        int c[10004], w[10004], dp[10004];
        while(scanf("%d %d", &n, &v) != EOF)
        {
            memset(dp, 0, sizeof(dp));
            for(i = 0; i < n; i++)
            {
                scanf("%d", &w[i]);
            }
            for(i = 0; i < n; i++)
            {
                scanf("%d", &c[i]);
            }
            for(i = 0; i < n; i++)
            {
                for(j = 0; j <= v; j++)
                {
                    if(j >= c[i])
                    {
                        dp[j] = Max(dp[j], dp[j-c[i]] + w[i]);
                        //printf("i:%d\ndp[%d]: %d \n",i, j, dp[j]);
                    }
                }
            }
            printf("%d\n", dp[v]);
        }
        return 0;
    }
    
    
    /***************************************************
    User name: jk160630
    Result: Accepted
    Take time: 392ms
    Take Memory: 220KB
    Submit time: 2017-02-10 14:50:17
    ****************************************************/

hint:  
1 背包体积v：背包体积  
物品体积c\[i\]：物品体积  
物品价值w\[i\]：物品价值  
完全背包判断依据之一：每种物品有无数种

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2007/pid/2826