CodeForces-189A Cut Ribbon-必须装满的背包

题意：

给定n，

s.t.  a1*x1+a2*x2+a3*x3=n（1）

max:x1+x2+x3

对比完全背包，（1）式取等号而不是<=

这个差别影响了我们的结果

比如：

n=7，a1=a2=5,a3=2

如果按照完全背包的转移：

则在dp[7]=3,也就是2+2+2

但背包并没有装满

装满的方案是：dp[7]=2，也就是2+5

那么我们在枚举容量的时候，不能去涉及那些减不完的状态

我们只能枚举，j=2(=4=6),h=5,这时就避免了：dp[5]=max(dp[5],dp[5-2]+1)=2,因为3是没办法凑满的

设置初始量为-1，dp[0]=0->dp[2]=max(dp[2],dp[2-2]+1),这时候需要dp[0]=0

#include<bits/stdc++.h>
using namespace std;
const int maxw=4e3+1e1;
int w[3],dp[maxw];

int main()
{
    int n;cin>>n;
    for(int i=0;i<3;i++)cin>>w[i];
    fill(dp,dp+maxw,-1);
    dp[0]=0;
    for(int i=0;i<3;i++)
    {
        for(int j=w[i];j<=n;j++)
        {
            if(dp[j-w[i]]!=-1)
            {
                dp[j]=max(dp[j],dp[j-w[i]]+1);
            }
        }
    }
    cout<<dp[n]<<"\n";
    return 0;
}