//
// main.cpp
// project1
//
// Created by Roger on 14-8-30.
// Copyright (c) 2014年 Roger. All rights reserved.
//
#include <iostream>
using namespace std;
int main()
{
int v,c,i,j;
int vv[31],value[31],f[31][20001];
cin>>v>>c;
for (i=1;i<=c;cin>>vv[i],value[i]=vv[i],i++);
for (i=0;i<=c;i++)
{
for(j=0;j<=v;j++) f[i][j]=0;
}
for (i=1;i<=c;i++)
{
for (j=v;j>=vv[i];j--)
{
f[i][j]=f[i-1][j];
if (j>=vv[i]&&(f[i-1][j-vv[i]]+value[i])>f[i][j]) f[i][j]=f[i-1][j-vv[i]]+value[i];
}
}
cout<<v-f[c][v];
return 0;
}
4 条评论
-
niushi LV 8 @ 2015-12-02 17:16:16
数组没开够，我已开始也是这样
-
@ 2014-11-10 18:55:08
我知道了 ！！ 数组 没开够==
-
@ 2014-11-10 18:37:08
#include<iostream>
#include<cstring>
using namespace std;
int f[31][200001];
int main()
{
int v,n,w[30];
memset(w,0,sizeof(w));
memset(f,0,sizeof(f));
cin>>v>>n;
for(int i=1;i<=n;i++)
{
cin>>w[i];
}for(int i=0;i<=v;i++)
{
if(i>=w[n])
f[n][i]=w[n];
}for(int i=n-1;i>0;i--)
{
for(int j=0;j<=v;j++)
{
f[i][j]=f[i+1][j];
if(j>=w[i]&&(f[i+1][j-w[i]]+w[i]>f[i+1][j]))
{
f[i][j]=f[i+1][j-w[i]]+w[i];
}
}
}
/*
for(int i=1;i<=n;i++)
{
for(int j=0;j<=v;j++)
{
cout<<f[i][j]<<" ";
}
cout<<endl;
}*/
cout<<v-f[1][v]<<endl;return 0;
}我也不明白 为什么 我的为什么runtime !!
-
@ 2014-11-07 17:56:33
f定为全局即可
- 1
