背包计数

给出背包的容量W、物品费用,每件物品只能取一次，求装满背包的方案总数以及最优方案总数（使物品总价值最大的方案，这里背包不需要装满）

输入描述

第一行有一个数k,代表有k组样例，每组样例有n+1行,第一行有两个数n,W,分别代表物品的件数，和背包容量，接下来为n行 每行有两个数，物品的费用c、物品的价值w

输出描述

每个样例输出一行，包含两个数：装满背包的方案总数以及最优方案总数，中间用空格隔开

样例输入

1
1 10
2 3

样例输出

0 1

装满背包的方案总数简单

最优方案总数

if(f[j].p<f[j-s[i].c].p+s[i].w) 更新数据

if(f[j].p==f[j-s[i].c].p+s[i].w)累加次数 f[j].num+=f[j-s[i].c].num;

同时注意

最优方案总数>=1

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
int dp[109];

struct data
{
    int c,w;
}s[109];

struct da
{
    int num,p;
}f[109];

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,i,v,j;
        scanf("%d%d",&n,&v);
        for(i=0;i<=v;i++)
        {
            dp[i]=0;f[i].num=0;f[i].p=0;
        }
        dp[0]=1;

        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&s[i].c,&s[i].w);
        }

        for(i=1;i<=n;i++)
        {
            for(j=v;j>=s[i].c;j--)
            {
                if(dp[j-s[i].c]!=0)
                    dp[j]+=dp[j-s[i].c];
            }
        }
        printf("%d ",dp[v]);
        
        f[0].num=1;
        int mmax=0,add=1;
        for(i=1;i<=n;i++)
        {
            for(j=v;j>=s[i].c;j--)
            {
                if(f[j-s[i].c].num!=0)
                {
                    //f[j].p=max(f[j].p,f[j-s[i].c].p+s[i].w);
                    if(f[j].p<f[j-s[i].c].p+s[i].w)
                    {
                        f[j].p=f[j-s[i].c].p+s[i].w;
                        f[j].num=f[j-s[i].c].num;
                        continue;
                    }
                    if(f[j].p==f[j-s[i].c].p+s[i].w)
                        f[j].num+=f[j-s[i].c].num;
                }
            }
        }

        for(i=1;i<=v;i++)
        {
            mmax=max(f[i].p,mmax);
        }
        int all=0;
        for(i=0;i<=v;i++)//一开始没有注意最优解最少有一个！！WA好久
        {
            if(f[i].p==mmax)
            {
                all+=f[i].num;
            }
        }
        printf("%d\n",all);
    }

    return 0;
}