hdoj 2602 Bone Collector【01背包】

深藏阁楼爱情的钟 2022-08-09 06:45 18阅读 0赞

# Bone Collector #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 41096    Accepted Submission(s): 17103**

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

题目大意：一个人有一个容量为V的背包，现在要收集骨头，每个头骨都有不同的价值和体积，在路边有n块骨头，哪些骨头可要，哪些骨头不要，才能在不溢出的情况下拿到价值更多的骨头。【笔者原来还不知道是用01背包，我以为普通的贪心就可以过了，结果可想而知】

Sample Input

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

Sample Output

分析：

例如 骨头数目为5，背包容量为10，

骨头  1 2 3 4 5

价值  1 2 3 4 5

体积  5 4 3 2 1

每个骨头都有两种状态，放或者不放【1,0】，那么就可以转化为一个只牵扯前 i - 1 个骨头的问题，如果不放第i个骨头，那么问题就转化为“前i-1件骨头放入容量为v的背包中”，价值为f\[i-1\]\[v\]；如果放第i个骨头，那么问题就转化为“前i-1个骨头放入剩下的容量为v-c\[i\]的背包中”，此时能获得的最大价值就是f\[i-1\]\[v-c\[i\]\]再加上通过放入第i个骨头获得的价值w\[i\]。

已Accept代码：

#include <stdio.h>
    #include <string.h>
    int f[1002], c[1002], w[1002];
    int main() {
        int t, n, v, i, j;
        scanf("%d", &t);
        while(t--) {
            memset(f, 0, sizeof(f));
            memset(c, 0, sizeof(w));
            memset(w, 0, sizeof(c));
            scanf("%d%d", &n, &v);
            for(i = 1; i <= n; i++)
                scanf("%d", &c[i]);
            for(i = 1; i <= n; i++)
                scanf("%d", &w[i]);
            for(i = 1; i <= n; i++)
                for(j = v; j >= w[i]; j--)
                    f[j] = f[j] > f[j - w[i]] + c[i] ? f[j] : f[j - w[i]] + c[i];
            printf("%d\n", f[v]);
        }
        return 0;
    }

下面是闲的蛋疼，用dfs做的，结果超时了

有兴趣的可以看看

#include <cstdio>
    #include <cstring>
    using namespace std;
    int n, V, Max;
    int v[1001], t[1001]; 
    
    void dfs(int total,int k, int c) {
    	if(Max < k)
    		Max = k;
    	if(c >= n)
    		return ;
    	for(int j = 0; j <= 1; j++) {
    		if(!j)
    			dfs(total, k, c + 1);
    		else {
    			if(total >= t[c])
    				dfs(total - t[c], k + v[c], c + 1);
    			else
    				dfs(total, k, c + 1);
    		}
    	}
    	return ;
    }
    
    int main() {
    	int T;
    	scanf("%d", &T);
    	while(T--) {
    		Max = 0;
    		scanf("%d%d", &n, &V);
    		for(int i = 0; i < n; i++)
    			scanf("%d", &v[i]);
    		for(int i = 0; i < n; i++)
    			scanf("%d", &t[i]);
    		dfs(V, 0, 0);
    		printf("%d\n", Max);
    	}
    	return 0;
    }