P1016 （C++代码）

解题思路:





注意事项:





参考代码:

大佬来帮大家解决问题啦！！！！！

1.简单的DFS，剪一下枝即可
求剩余最少，只要求小于v的条件下最大


    #include <iostream>
    using namespace std;    
    int v,n,a[31],t,maxx;  
      void dfs(int k)
    {        if(t > v)            return;//剪枝
        if(k > n)
        {            if(t > maxx)
                maxx=t;            return;
        }        else
        {
            t+=a[k];
            dfs(k+1);
            t-=a[k];
            dfs(k+1);            return;
        }
    }    int main()
    {        
    cin>>v;        
    cin>>n;       
     for(int i=1;i<=n;i++)          
       cin>>a[i];
        dfs(1);        
        cout<<v-maxx;//剩余部分
        }
        
2.这道题看似是搜索，但是可以用背包做。
题目要求求出最小的剩余空间，也就是要求出最大的可装重量
这样，我们可以将一个物体的重量当作它的价值，进而将题目转变为一个基本的01背包问题：
有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）和一个价值（等于体积）。
要求n个物品中，任取若干个装入箱内，使总价值最大。
对于每一个物体，都有两种状态：装 与不装
那么，对于任意重量m的最大价值 f (m) = max ( f ( m - w[i] ) + w[i], f (m) )（w为重量（即价值））
其中，f ( m - w[i] ) 指在装了物品i后，箱子的剩余容量能装的最大重量
f ( m - w[i] ) + w[i] 指在在装了物品i后，箱子能装的最大重量

程序如下：
#include<cstdio>
using namespace std;int m,n;                \\m即箱子容量Vint f[20010];int w[40];
int main(){    int i,j;    scanf("%d%d",&m,&n);    
for(i=1;i<=n;i++){        scanf("%d",&w[i]);
    }    for(i=1;i<=n;i++){        
    for(j=m;j>=w[i];j--)
    {  \\注意：这里必须是从m到w[i]，否则一个物体会被多次装入箱子，见例1
            if(f[j]<f[j-w[i]]+w[i]){
                f[j]=f[j-w[i]]+w[i];
            }
        }
    }    printf("%d\n",m-f[m]);
}
例1： 输入：
5 1 1 假如在遍历容量m时从小到大遍历，你会发现:
f (2) = f (2 - 1) + w[1] = f (1) +w[1] = 2
f (3) = ... = 3
f (4) = 4
f (5) = 5
最后的答案就是5-5=0，然而正解是5-1=4

3.第一次练习一下bitset
原理和前面题解的bool dp是一样的
只是用bitset和位运算加速了而已
当然普及是完全用不上的


code:
    #include<bits/stdc++.h>
    #define LL long long
    #define clr(x,i) memset(x,i,sizeof(x))
    using namespace std;    const int N=20505;    bitset<N> a;    int n,v;    int main()
    {        scanf("%d%d",&v,&n);        int x;        for(int i=1;i<=n;i++)
        {            scanf("%d",&x);
            a|=(a<<x);
            a[x-1]=1;            //for(int j=0;j<=v;j++)
              //printf("%d ",a[j] ? 1 : 0);
            //putchar('\n');
        }        for(int i=v-1;i>=0;i--)          
        if(a[i]){              
        printf("%d",v-i-1);break;
          }        return 0;
    }