HDU 2546 饭卡（01背包） 解题报告

昨天吧背包九讲中最基础的01背包看完，做了2602。结果晚上比赛相同题目却做不出。。苦想几个小时。。。
解题思路：要使剩余钱最少，应该留下块钱买最贵的东西（标记为t）（注意金额m<5 的情况！！） 接下来就是用剩下的m-5元买除t以外的菜。每种菜只能买一次。就构成背包问题。

代码：

[cpp]
#include<stdio.h> 
#include<math.h> 
#include<string.h> 
#include<stdlib.h> 
#include<algorithm> 
#include<iostream> 
using namespace std; 
int main() 
{ 
    int n,m,w[1050],v[1050]; 
    while(scanf("%d",&n) && n) 
    { 
        memset(v,0,sizeof(v)); 
        int ma=0,t,i,s=0; 
        for(i=1;i<=n;i++) 
        { 
            scanf("%d",&w[i]); 
            if(w[i]>ma){ma=w[i]; t=i;} 
        } 
        scanf("%d",&m); 
        if(m<5) 
        { 
            printf("%d\n",m); 
            continue; 
        } 
        for(i=1;i<=n;i++) 
        { 
            for(int j=m;j>=w[i];j--) 
            { 
                if(i!=t && v[j-w[i]]+w[i]>v[j]) 
                    v[j]=v[j-w[i]]+w[i]; 
            } 
             
        } 
        printf("%d\n",m-v[m-5]-ma); 
    } 
    return 0; 
} 

补充：软件开发 , C++ ,

上一个：c++ 前置声明不能随便用 会引起类型不完全的错误
下一个：poj3268---spfa