Sicily 1342楽しい金明
2つの方法、DFSとdpリュックサック.
DFSコード
dpコード
DFSコード
#include <iostream>
using namespace std;
#include <stdio.h>
struct object {
int price;
int id;
bool flag;
};
int n,m;
struct object ob[ 25 ];
struct object sel[ 25 ];
int ctr = 0;
int max0 = 0;
void solve( int sum, int k ) {
int i,j;
int s=0;
// cout << k << endl;
if ( sum == n ) {
s=0;
for ( i=0;i<ctr;i++ ) {
s=s+sel[i].price*sel[i].id;
}
if ( s > max0 )
max0 = s;
}
else if ( sum < n ) {
s=0;
for ( i=0;i<ctr;i++ ) {
s=s+sel[i].price*sel[i].id;
}
if ( s > max0 )
max0 = s;
for ( j=k;j<m;j++ ) {
if ( sum+ob[j].price <= n ) {
sum=sum+ob[j].price;
sel[ctr]=ob[j];
ctr++;
ob[j].flag=false;
solve( sum, j+1 );
ctr--;
ob[j].flag=true;
sum=sum-ob[j].price;
}
}
}
}
int main()
{
int i;
while ( scanf( "%d", &n ) != EOF ) {
scanf( "%d",&m );
ctr=0;
max0=0;
for ( i=0;i<m;i++ ) {
cin >> ob[i].price >> ob[i].id;
ob[i].flag=true;
}
solve(0,0);
cout << max0 << endl;
}
return 0;
}
dpコード
#include <stdio.h>
#include <memory.h>
int n,m;
struct Object {
int v,p;
};
Object o[30];
int dp[30001];
int get_max(int a, int b) {
if (a>b)
return a;
else
return b;
}
int main() {
int i,j;
while (scanf("%d",&n)!=EOF) {
scanf("%d",&m);
for (i=0;i<m;i++)
scanf("%d%d",&o[i].v, &o[i].p);
memset(dp,0,sizeof(dp));
for (i=0;i<m;i++) {
for (j=n;j>=o[i].v;j--) {
dp[j] = get_max(dp[j], dp[j-o[i].v]+o[i].v*o[i].p);
}
}
printf("%d
", dp[n]);
}
return 0;
}