简化型背包—C语言(DFS深度搜索)(用不了DP)

解题思路:

1、这个相单于数学的组合问题。

2、DFS可以看做是列出树状图，先从最大的大树0开始，他的子树有树1，树2，树3，树4，树5（也就是5个物品）。然后他从树1开始找，树1就沿自己的根到另一个子树(其他剩下的树中的树2开始)，再从子树（树2）的根到 它的子树（树3），沿着根一直往下累加物品的价值sum...... ，当沿着根一直向下走后不满足条件了，就将现在拥有的价值与最终价值ans比较，大于就更新ans，否则不更新。    当树1全部查找完了后，并且也对比出了树1所有路线中的某条最大价值后，就开始来到了树2，树2也同理这样找，并且得最大的价值，再到树3。。。。

这段代码如下：

void dfs(int x,int W, int V, int sum, int* ans, int w[], int v[], int p[],int maxW,int maxV)
{
    sum = sum + p[x];
    W = W + w[x];
    V = V + v[x];
    *ans=max(*ans, sum);
    if(W>=maxW || V>=maxV)
    {
        return;
    }
    for(int j=x+1;j<6;j++)
    {
        if(W+w[j]<=maxW && V+v[j]<=maxV)
        {
            dfs(j, W, V, sum, ans, w, v, p, maxW, maxV);
        }
    }
}

3、以此类推到 树5找完后就可以的最终满足条件的最大价值

注意事项:

1、从哪个树开始，它的子树只需要从这棵树后面的树开始

如从树2开始，搜索它的子树就从树3开始（判断符不符合条件），而子树树3就从它的子树4开始（判断符不符合条件），子树树4就从它的子树5开始（判断符不符合条件）。这样就可以完成一次查找。

可以画出树状图，就很容易理解
参考代码:

#include<stdio.h>
int max(int num1,int num2)
{
    if (num1 > num2)return num1;
    return num2;
}
void dfs(int x,int W, int V, int sum, int* ans, int w[], int v[], int p[],int maxW,int maxV)
{
    ////x为第几个物,W为到目前为止背包重量，V为到目前为止背包的体积
	//sum为到目前为止背包的价值（不一定最大），ans记录最终的最大价值
	//w存每个物品的重量，v存每个物品的体积，p存每个物品的价值
	//maxW题目规定的最大重量
	//maxV题目规定的最大体积

    sum = sum + p[x];
    W = W + w[x];
    V = V + v[x];
    *ans=max(*ans, sum);
    if(W>=maxW || V>=maxV)
    {
        return;
    }
    for(int j=x+1;j<6;j++)//本树的下一棵树开始
    {
        if(W+w[j]<=maxW && V+v[j]<=maxV)//本树是否可以到下一棵树
        {
            dfs(j, W, V, sum, ans, w, v, p, maxW, maxV);//传入本树到目前为止的信息
        }
    }
}
void test87()
{
    int ans = 0;
    int w[6] = { 0 };
    int v[6] = { 0 };
    int p[6] = { 0 };
    int sum = 0;
    int maxW = 0;
    int W = 0;
    int maxV = 0;
    int V = 0;
    scanf("%d %d", &maxV, &maxW);
    for(int i=1;i<6;i++)
    {
        scanf("%d %d %d", &p[i], &v[i], &w[i]);
    }
    dfs(0,W, V, 0, &ans, w, v, p,maxW,maxV);
    printf("%d", ans);
 
}
int main()
{
test87();
    return 0;
}