hdu 1248

http://acm.hdu.edu.cn/showproblem.php?pid=1248

唉。。。这题，我不会完全背包问题，只能暴力了，还好数据比较弱，果断过了，但是用暴力方法过的感觉很不爽啊。

代码如下：

#include"stdio.h"

int main( )
{
    int i,j,k,n,a,b,c,t;
    int max,x,y,z;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        max=0;
        a=n/150;b=n/200;c=n/350;
        for(i=0;i<=c;i++)
        {
            x=350*i;
            for(j=0;j<=b;j++)
            {
                y=200*j;
                if(x+y>n)
                    break;
                for(k=0;k<=a;k++)
                {
                    z=150*k;
                    if(x+y+z>n)
                        break;
                    if(max<x+y+z)
                        max=x+y+z;
                }
            }
        }
        printf("%d\n",n-max);
    }
    return 0;
}
            

以下代码为完全背包代码：

#include <iostream>
using namespace std;


int main()
{
    int coin[3] = {150, 200, 350};
    int t, i, j, n;
    
    int dp[100005];
    cin>>t;
    while(t--)
    {
        cin>>n;
        
        memset(dp,0,sizeof(dp));
        
    
        
        for(i = 0; i < 3; i++)
        {
            for(j = coin[i]; j <= n; j++)
            {
                if(dp[j] < dp[j-coin[i]]+coin[i])   //这块加一个判断、、、
                    dp[j] = dp[j-coin[i]] + coin[i];
            }
        }
        
        cout<<n-dp[n]<<endl;
    }
    
    return 0;
}