http://acm.hdu.edu.cn/showproblem.php?pid=2159&&二次元完全リュックサック
676 ワード
最初の考えは完全リュックサックを0-1バックに変えて解くことです.ずっとwa、最後にネットで検索してみました.二次元完全リュックサックです.dp[i][j]は、許容度がiの敵数がj個という最大の経験を示しています.
#include<iostream>
#include<string.h>
using namespace std;
int dp[101][101];
int v[101],w[101];
int n,m,k,s;
int main()
{
int i,j,p;
while(cin>>n>>m>>k>>s)
{
memset(dp,0,sizeof(dp));
for(i=1;i<=k;++i)
cin>>v[i]>>w[i];
bool flag=0;
for(i=1;i<=m;++i)// 。
{
for(j=1;j<=k;++j)//
for(p=1;p<=s;++p)//
if(i>=w[j])
dp[i][p]=max(dp[i][p],dp[i-w[j]][p-1]+v[j]);
if(dp[i][s]>=n) break;
}
cout<<m-i<<endl;
}return 0;
}