完全背包問題。
以下是我的代碼：
#include<iostream>
#define maxn 107
#define maxm 17
#define inf 20000007
using namespace std;
long min(long a,long b){return (a<b?a:b);}
long n,w[maxm],c[maxm],d[maxn];
int main()
{
for(long i=1;i<=10;i++)
{
cin>>c[i];
w[i]=i;
}
cin>>n;
// Input
d[0]=0;
for(long i=1;i<=n;i++)
d[i]=inf;
for(long i=1;i<=10;i++)
for(long j=w[i];j<=n;j++)
d[j]=min(d[j],d[j-w[i]]+c[i]);
// DP
cout<<d[n]<<endl;
// Output
return 0;
}
posted on 2010-10-18 15:16
lee1r 閱讀(285)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃