题目链接

给你n个物品的价值，以及一个总背包容量V，让你求有多少种方法使得背包里装了一些东西（可以不装）并且剩下的物品中最小的那一个也装不进背包。

思路：枚举每个物品，当它作为剩余物品中最小价值的那一个的时候，比它价值小的一定都放进了背包里，所以当前的背包容量区间为[m-a[i]+1,m]；对剩下的进行01背包

由于使用了01背包，所以按照物品的价值从大到小遍历一遍，枚举每个物品为剩余的最小价值这样复杂度为O(n*m)

 

 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
const int maxn=1e5+5;
using namespace std;
int T, n, V, t = 1, sum, ans;
int dp[1010], a[1010];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        sum=ans=0;
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        scanf("%d%d",&n,&V);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i];
        sort(a+1,a+1+n);
        for(int i=n;i>=1;i--) {
            sum-=a[i];
            if(a[i]>V)continue;
            for(int j=0;j<a[i]&&V-sum-j>=0;j++) {
                ans+=dp[V-sum-j];
            }
            for(int j=V;j>=a[i];j--)
                dp[j]+=dp[j-a[i]];
        }
        printf("%d %d\n",t++,ans);
    }
    return 0;
}