リュックサック問題のいくつかのテーマ！
11588 ワード
hdu 1203
タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=1203
各商品のコスプレはa[i]であり、価値はb[i]と関係があり、簡単な01バックパックの問題である。
ACコード:
タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=2602
典型的な01のリュックサックは直接コードに会います。
タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=1171
n個の荷物がありますが、一つ一つの商品の価値と数量が違っています。完全なバックパックの問題です。数量が大きくないので、01個のバックパックに変えられます。
ACコード:
タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=1864
リュックサックの問題みたいですが、バックパックはintが必要です。答えは2人分の有効な数字が必要なので、リュックサックのコストを100倍に拡大して、バックパックの容量を100倍に拡大しますが、これは多少の精度の損失があります。01リュックサック
タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=1712
タイトルはn個の宿題があります。j日間でi番目の宿題を完成すれば、wei[i][j]の価値が得られます。ですから、ミッションごとに完成しないか、それとも一回だけ完成するか、完全なリュックサックの問題です。まずバックパック9の内容を見てもいいです。
for すべてのグループk
for v=V..0
for 全てのiはグループkに属する。
f[v]=max｛f[v]，f[v-c[i]＋w[i]｝
各グループの中で一番多くて一つしか選べないという意味です。
ACコード:
タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=2660
まず、n、kをあげます。n個の品物があります。下は順にn個のもののcosとweiです。そして、バックパックの容量はvolです。ただし、条件があります。バックパッキングの荷物の数はkより多くないので、二次元の01個のバックパックを使う必要があります。dp[l][j]は容量がlで、最大j個の荷物を入れる時に最大の値を入れます。状態遷移方程式は dp[l][j]=max(dp[l]、[j]，dp[l-cos[i]、[j-1]+wei[i]
ACコード:
タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=1709
いくつかの数字を与えて、分銅として、どれが量れないかを見ます。まず1つのバックパックに加算できるすべての状況を求めて、量れる重量を見つけて、減法が使える状況を暴力的に探してください。
ACコード:
タイトルの住所:http://poj.org/problem?id=3624
スタンダードな01バックパックです。。
昼は停電して網が切れて、血が全然なくなりました。
ACコード:
タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=2159
題目：中国語のテーマは説明しません。二次元完全リュックサックの標準問題です。
ACコード:
タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=2844
多重リュックサック、タイトルはn種の金貨にあげる金額です。金額はmを超えてはいけません。そして各金貨のv[i]を入力してください。c[i]はそれぞれこの金貨の代表金額とこの金貨の数量を表しています。これらの金貨を出力したいですが、mを超えない金額はいくらですか？
典型的な二次元多重リュックサックのテーマ。
普通の多重リュックサックの解法をすれば、O(n*m*c)nは荷物の種類の数です。mはリュックの容量です。cは商品の種類ごとに該当する数です。このテーマを適用すれば、10^7*10^3=10^10の時間の複雑さです。もちろん、不可能です。もちろん、複雑度をO（n＊m）に下げることができますが、各用品の個数を記録するために多くの配列を作る必要があります。コードを参照してください
タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=2191
バックパックの容量をvolしてあげます。そして、n種類のものをあげます。それぞれの商品に価値があります。体積もあります。もちろん、各商品の数量もあります。典型的な多重リュックサックは、種類が最大100なので、荷物の数は最大20個までです。01個のバックパックの総量を最大2*10^3に変えてからバックパックの容量100,10^5に乗ると、複雑さが受け入れられます。
ACコード:
タイトルの住所:http://poj.org/problem?id=2392
あなたにk種の石をあげます。一つ一つの石は高さhと最高のエネルギーがある高さaと数量cがあります。これらの石で積み上げた最高の高さを聞きます。
私たちはこれらの石の高さを低いから高い順に並べて、そのまま完全なリュックサックのコースを使えばいいです。
例えば
2
8 15 1
3 8 3
並べ替え後の最大高さは14で、並べ替えなしの最大高さは8です。
ACコード:
タイトルの住所:http://poj.org/problem?id=2184
テーマは牛のs値とf値をあげます。これらの牛の中からs値の和>=0、f値の和'=0を保証する上で、s値とf値の和を最大にします。
まずこのタイトルを見たらリュックサックを思い出します。そして、01リュックサックですが、中に負数があります。手で移動して、右に移動すればいいです。私たちがしたいのはdp[s]バックパックでfを背负うことです。sが一定の状况でfが一番大きいということです。もちろん、私たちも01バックパックの循环の顺序を覚えています。だから、s[i]の正と負の値によって、循环の顺序を考えなければなりません。詳細はコードを参照:
ACコード:
タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=1203
各商品のコスプレはa[i]であり、価値はb[i]と関係があり、簡単な01バックパックの問題である。
ACコード:
#include
#include
#include
#include
using namespace std;
double dp[10005];
int a[10005];
double b[10005];
int main()
{
int n,m,i,j;
while(cin>>n>>m&&n+m)
{
for(i=0;i>a[i]>>b[i];
memset(dp,0,sizeof(dp));
for(i=0;i=a[i];j--)
dp[j]=max(dp[j],1-(1-dp[j-a[i]])*(1-b[i]));
double res=dp[n]*100;
printf("%.1f%%
",res);
}
return 0;
}
タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=2602
典型的な01のリュックサックは直接コードに会います。
#include
#include
#include
using namespace std;
int dp[1002],i,j,num,vol;
int cos[1002],wei[1002];
void ZeroOnePack(int cost,int weight)
{
for(j=vol;j>=cost;j--)
if(dp[j]>tes;
while(tes--)
{
cin>>n>>vol;
for(i=0;i タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=1171
n個の荷物がありますが、一つ一つの商品の価値と数量が違っています。完全なバックパックの問題です。数量が大きくないので、01個のバックパックに変えられます。
ACコード:
//
// sum/2
// n*m<=5000 . 5000*50/2<2*10^5
#include
#include
#include
using namespace std;
int dp[200005];
int wei[5005];
int main()
{
int t,i,j,n,v,m,sum;
while(cin>>t&&t>0)
{
n=sum=0;
memset(dp,0,sizeof(dp));
for(i=0;i>v>>m;
sum+=v*m;
while(m--)
wei[n++]=v;
}
for(i=0;i=wei[i];j--)
dp[j]=max(dp[j],dp[j-wei[i]]+wei[i]);
cout< タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=1864
リュックサックの問題みたいですが、バックパックはintが必要です。答えは2人分の有効な数字が必要なので、リュックサックのコストを100倍に拡大して、バックパックの容量を100倍に拡大しますが、これは多少の精度の損失があります。01リュックサック
#include
#include
#include
#include
using namespace std;
double wei[35],dp[3000005];
int main()
{
double sum,sa,sb,sc,money;
int t,n,q,i,j;
int flag;
char c;
while(cin>>sum>>t&&t)
{
n=0;
memset(dp,0,sizeof(dp));
while(t--)
{
cin>>q;
sa=sb=sc=0; // A，B，C
flag=0;
while(q--)
{
scanf(" %c:%lf",&c,&money);
if(c'C'||money>600) // >600
flag=1;
if(c=='A') sa+=money;
else if(c=='B') sb+=money;
else if(c=='C') sc+=money;
}
if(!flag&&sa+sb+sc<=1000&&sa<=600&&sb<=600&&sc<=600)
wei[n++]=sa+sb+sc;
}
int isum=sum*100;
for(i=0;i=iwei;j--) // 100
dp[j]=max(dp[j],dp[j-iwei]+wei[i]);
}
printf("%.2lf
",dp[isum]);
}
return 0;
}
/*
200.00 3
2 A:23.50 B:100.00
1 C:650.00
3 A:59.99 A:120.00 X:10.00
1200.00 2
2 B:600.00 A:400.00
1 C:200.50
1200.50 3
2 B:600.00 A:400.00
1 C:200.50
1 A:100.00
100.00 0
1000 4
1 A:300
1 B:300
1 A:200
1 C:500
*/
タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=1712
タイトルはn個の宿題があります。j日間でi番目の宿題を完成すれば、wei[i][j]の価値が得られます。ですから、ミッションごとに完成しないか、それとも一回だけ完成するか、完全なリュックサックの問題です。まずバックパック9の内容を見てもいいです。
for すべてのグループk
for v=V..0
for 全てのiはグループkに属する。
f[v]=max｛f[v]，f[v-c[i]＋w[i]｝
各グループの中で一番多くて一つしか選べないという意味です。
ACコード:
#include
#include
#include
using namespace std;
int wei[105][105];
int dp[105];
int main()
{
int n,m,i,j,k;
while(cin>>n>>m&&n+m)
{
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&wei[i][j]);
for(i=1;i<=n;i++) // n
for(j=m;j>=0;j--) // j
for(k=1;k<=m;k++) // k i
if(j>=k)
dp[j]=max(dp[j],dp[j-k]+wei[i][k]);
cout< タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=2660
まず、n、kをあげます。n個の品物があります。下は順にn個のもののcosとweiです。そして、バックパックの容量はvolです。ただし、条件があります。バックパッキングの荷物の数はkより多くないので、二次元の01個のバックパックを使う必要があります。dp[l][j]は容量がlで、最大j個の荷物を入れる時に最大の値を入れます。状態遷移方程式は dp[l][j]=max(dp[l]、[j]，dp[l-cos[i]、[j-1]+wei[i]
ACコード:
#include
#include
#include
using namespace std;
int dp[1002][21],i,j,vol,k,l;
int cos[1002],wei[1002];
int main()
{
int T;
cin>>T;
while(T--)
{
memset(dp,0,sizeof(dp));
int n;
scanf("%d%d",&n,&k);
for(i=0;i=cos[i];l--)
for(j=1;j<=k;j++)
dp[l][j]=max(dp[l][j],dp[l-cos[i]][j-1]+wei[i]);
printf("%d
",dp[vol][k]);
}
return 0;
}
タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=1709
いくつかの数字を与えて、分銅として、どれが量れないかを見ます。まず1つのバックパックに加算できるすべての状況を求めて、量れる重量を見つけて、減法が使える状況を暴力的に探してください。
ACコード:
#include
#include
#include
#include
using namespace std;
int dp[10005];
int vis[10005];
int xx[10005];
int res[10005];
int a[105],sum,n,t;
void onepack(int cost,int weight)
{
int l;
for(l=sum;l>=cost;l--)
if(dp[l]0)
{
for(i=0;i タイトルの住所:http://poj.org/problem?id=3624
スタンダードな01バックパックです。。
昼は停電して網が切れて、血が全然なくなりました。
ACコード:
#include
#include
#include
using namespace std;
int dp[15000];
int cos[5000],wei[5000];
int main()
{
int i,j,n,vol;
while(cin>>n>>vol)
{
memset(dp,0,sizeof(dp));
for(i=0;i>cos[i]>>wei[i];
for(i=0;i=cos[i];j--)
dp[j]=max(dp[j],dp[j-cos[i]]+wei[i]);
cout< タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=2159
題目：中国語のテーマは説明しません。二次元完全リュックサックの標準問題です。
ACコード:
#include
#include
#include
using namespace std;
int dp[105][105];
int wei[105],cos[105];
int main()
{
int i,j,k;
int n,m,K,s;
while(cin>>n>>m>>K>>s)
{
for(i=0;i=cos[i])
dp[j][k]=max(dp[j][k],dp[j-cos[i]][k-1]+wei[i]);
}
}
}
if(dp[m][s]=n)
res=min(res,i);
}
res=m-res;
cout< タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=2844
多重リュックサック、タイトルはn種の金貨にあげる金額です。金額はmを超えてはいけません。そして各金貨のv[i]を入力してください。c[i]はそれぞれこの金貨の代表金額とこの金貨の数量を表しています。これらの金貨を出力したいですが、mを超えない金額はいくらですか？
典型的な二次元多重リュックサックのテーマ。
普通の多重リュックサックの解法をすれば、O(n*m*c)nは荷物の種類の数です。mはリュックの容量です。cは商品の種類ごとに該当する数です。このテーマを適用すれば、10^7*10^3=10^10の時間の複雑さです。もちろん、不可能です。もちろん、複雑度をO（n＊m）に下げることができますが、各用品の個数を記録するために多くの配列を作る必要があります。コードを参照してください
#include
#include
#include
using namespace std;
const int maxn=100005;
int visi[maxn];
int used[maxn];
int v[105],c[105];
int main()
{
int n,m;
int i,j;
while(cin>>n>>m&&n+m)
{
for(i=0;i>v[i];
for(i=0;i>c[i];
int res=0;
memset(visi,0,sizeof(visi));
visi[0]=1;
for(i=0;i タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=2191
バックパックの容量をvolしてあげます。そして、n種類のものをあげます。それぞれの商品に価値があります。体積もあります。もちろん、各商品の数量もあります。典型的な多重リュックサックは、種類が最大100なので、荷物の数は最大20個までです。01個のバックパックの総量を最大2*10^3に変えてからバックパックの容量100,10^5に乗ると、複雑さが受け入れられます。
ACコード:
#include
#include
#include
using namespace std;
int cos[2005],wei[2005];
int dp[105];
int main()
{
int tes;
cin>>tes;
int i,j;
while(tes--)
{
int vol,m;
cin>>vol>>m;
int num=0;
int a,b,c;
for(i=0;i>a>>b>>c;
for(j=0;j=cos[i];j--)
dp[j]=max(dp[j],dp[j-cos[i]]+wei[i]);
cout< タイトルの住所:http://poj.org/problem?id=2392
あなたにk種の石をあげます。一つ一つの石は高さhと最高のエネルギーがある高さaと数量cがあります。これらの石で積み上げた最高の高さを聞きます。
私たちはこれらの石の高さを低いから高い順に並べて、そのまま完全なリュックサックのコースを使えばいいです。
例えば
2
8 15 1
3 8 3
並べ替え後の最大高さは14で、並べ替えなしの最大高さは8です。
ACコード:
#include
#include
#include
#include
#include
#include
using namespace std;
int dp[40005];
int num[40005];
struct node
{
int h;
int a;
int c;
}block[405];
bool cmp(node p1,node p2)
{
return p1.a>k)
{
memset(dp,0,sizeof(dp));
dp[0]=1;
for(i=0;i>block[i].h>>block[i].a>>block[i].c;
sort(block,block+k,cmp);
int ans=0;
for(i=0;i タイトルの住所:http://poj.org/problem?id=2184
テーマは牛のs値とf値をあげます。これらの牛の中からs値の和>=0、f値の和'=0を保証する上で、s値とf値の和を最大にします。
まずこのタイトルを見たらリュックサックを思い出します。そして、01リュックサックですが、中に負数があります。手で移動して、右に移動すればいいです。私たちがしたいのはdp[s]バックパックでfを背负うことです。sが一定の状况でfが一番大きいということです。もちろん、私たちも01バックパックの循环の顺序を覚えています。だから、s[i]の正と負の値によって、循环の顺序を考えなければなりません。詳細はコードを参照:
ACコード:
#include
#include
using namespace std;
const int tab=1e5;
int s[105],f[105];
int dp[200005];
int main()
{
int n,i,j;
while(cin>>n)
{
for(i=0;i>s[i]>>f[i];
for(i=0;i<=2e5;i++)
dp[i]=-1e8;
dp[tab]=0;
int l=0,r=0;
for(i=0;i=l;j--)
{
dp[j+tab]=max(dp[j+tab-s[i]]+f[i],dp[j+tab]);
}
}
}
int res=0;
for(i=0;i<=r;i++)
{
if(dp[i+tab]>=0)
res=max(res,i+dp[i+tab]);
}
cout<