DAG上のダイナミックプランニング(トレーニングガイド-ホワイトブック)
6738 ワード
有向無ループ図(DAG,Directed Acyclic Graph)上のダイナミックプランニングはダイナミックプランニングを学習する基礎である.多くの問題は、DAG上の最長パス、最短パス、またはパスカウントの問題に変換できます.
一、矩形ネストテーマ記述:n個の矩形があり、各矩形は2つの整数a,bで記述することができ、その長さと幅を表す.矩形X(a,b)は、矩形Y(c,d)にネストされ、aE}Eはエッジセットであり、最終的な答えはd(i)である.辞書シーケンスの最小の最長パスを出力するように要求されたら?では、最初の最長パスの値を見つけて再帰的に出力する必要があります.
コード:
二、硬貨問題
タイトルの説明:
n種類の硬貨があり、額面はそれぞれV 1、V 2...、Vnは、どれも無限にあります.非負の整数Sを与えて、何個の硬貨を選んで、額面の和がちょうどSになるようにすることができますか?コイン数の最小値と最大値を出力します.0 <= n <= 100, 0 <= S <= 10000, 1 <= Vi <= S.
問題解決の考え方:
本題の本質はDAG上の経路問題である.各フェース値を1つの点として,「まだ十分なフェース値が必要である」と表すと,初期状態はS,目標状態は0である.現在の状態iでは、コインjが1つ使用されるごとに状態がi−Vjに移行する.このモデルはネストされた矩形の問題と似ているが,上の問題は経路の始点と終点を決定していない(任意の矩形を最初と最後に置くことができる)が,本問題の始点はSであり,終点は0でなければならないという明らかな違いもある.ゴールを固定してから「最短」が意味がある.ネストされた長方形では、最短シーケンスは明らかに空である(空が許されない場合は、単一の長方形であり、いずれにしても平凡である)が、本題の最短パスはそれほど容易に決定されない.
次に「コイン問題」を考えます.最長路と最短路の求め方は類似していることに気づき,以下では最長路のみを考慮する.終点が固定されているため、d(i)の正確な意味は「ノードiからノード0までの最長経路長」となる.
コード:
分析:本質的にDAG上の経路問題を上場し、私たちは各額面値を1つの点と見なし、まだ十分な額面値が必要であることを示し、初期状態は0、目標状態は0であり、現在iにある場合、硬貨jを1枚使用するたびに、状態はi-vjに移行する.
コード:
上のコードでは、出力パスが不要な場合はmax_coinsとmin_coins配列、次は再帰的なものを書きます.
最長経路を求めるもののみを記載しており、最短経路が要求される場合は最長経路と類似しており、ここでは省略する.
一、矩形ネストテーマ記述:n個の矩形があり、各矩形は2つの整数a,bで記述することができ、その長さと幅を表す.矩形X(a,b)は、矩形Y(c,d)にネストされ、a
コード:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std ;
const int MX = 1000 + 10 ;
int n ;
int G[MX][MX],dp[MX] ;
struct node
{
int x,y ;
}T[MX] ;
void buildGraph() //
{
memset(G,0,sizeof(G)) ;
for(int i=0 ;i<n ;i++)
for(int j=0 ;j<n ;j++)
if(T[i].x>T[j].x&&T[i].y>T[j].y)
G[i][j]=1 ;
}
int DAG(int x) //
{
int& ans = dp[x] ;
if(ans > 0) return ans ;
ans=1 ;
for(int i=0 ;i<n ;i++)
if(G[x][i])
{
int mx=DAG(i)+1 ;
ans = ans > mx ? ans : mx ;
}
return ans ;
}
void print(int x) //
{
printf("%d ",x) ;
for(int i=0 ;i<n ;i++)
if(G[x][i]&&dp[x]==dp[i]+1)
{
print(i) ;
break ;
}
}
int main()
{
int Tx ;
scanf("%d",&Tx) ;
while(Tx--)
{
scanf("%d",&n) ;
for(int i=0 ;i<n ;i++)
{
scanf("%d%d",&T[i].x,&T[i].y) ;
if(T[i].x>T[i].y)
swap(T[i].x,T[i].y) ;
}
int ans=1 ;
buildGraph() ;
memset(dp,-1,sizeof(dp)) ;
for(int i=0 ;i<n ;i++)
{
int mx=DAG(i) ;
ans= mx > ans ? mx : ans ;
}
for(int i=0 ;i<n ;i++)//
if(dp[i]==ans)
{
printf("%d
",ans) ;
print(i) ;
break ;
}
}
return 0 ;
}二、硬貨問題
タイトルの説明:
n種類の硬貨があり、額面はそれぞれV 1、V 2...、Vnは、どれも無限にあります.非負の整数Sを与えて、何個の硬貨を選んで、額面の和がちょうどSになるようにすることができますか?コイン数の最小値と最大値を出力します.0 <= n <= 100, 0 <= S <= 10000, 1 <= Vi <= S.
問題解決の考え方:
本題の本質はDAG上の経路問題である.各フェース値を1つの点として,「まだ十分なフェース値が必要である」と表すと,初期状態はS,目標状態は0である.現在の状態iでは、コインjが1つ使用されるごとに状態がi−Vjに移行する.このモデルはネストされた矩形の問題と似ているが,上の問題は経路の始点と終点を決定していない(任意の矩形を最初と最後に置くことができる)が,本問題の始点はSであり,終点は0でなければならないという明らかな違いもある.ゴールを固定してから「最短」が意味がある.ネストされた長方形では、最短シーケンスは明らかに空である(空が許されない場合は、単一の長方形であり、いずれにしても平凡である)が、本題の最短パスはそれほど容易に決定されない.
次に「コイン問題」を考えます.最長路と最短路の求め方は類似していることに気づき,以下では最長路のみを考慮する.終点が固定されているため、d(i)の正確な意味は「ノードiからノード0までの最長経路長」となる.
コード:
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#define INF 1<<30
#define maxn 100+10
using namespace std ;
int V[maxn],n;
int min[maxn],max[maxn];
inline int Min(int a,int b){return a<b?a:b;}
inline int Max(int a,int b){return a>b?a:b;}
//
void print_ans(int* d,int S)
{
for(int i=1;i<=n;i++)
{
if(S>=V[i] && d[S]==d[S-V[i]]+1)
{
printf("%d ",V[i]);
print_ans(d,S-V[i]);
break;
}
}
}
int main()
{
int S;
while(~scanf("%d%d",&S,&n)) // S n
{
for(int i=1;i<=n;i++)
scanf("%d",&V[i]);
max[0]=0; min[0]=0;
for(int i=1;i<=S;i++)
min[i]=INF,max[i]=-INF;
//
for(int i=1;i<=S;i++)
for(int j=1;j<=n;j++)
if(i>=V[j])
{
min[i]=Min(min[i],min[i-V[j]]+1);
max[i]=Max(max[i],max[i-V[j]]+1);
}
print_ans(min,S);
printf(" min
");
print_ans(max,S);
printf(" max
");
printf("min:%d max:%d
",min[S],max[S]);
}
return 0;
}分析:本質的にDAG上の経路問題を上場し、私たちは各額面値を1つの点と見なし、まだ十分な額面値が必要であることを示し、初期状態は0、目標状態は0であり、現在iにある場合、硬貨jを1枚使用するたびに、状態はi-vjに移行する.
コード:
#include<stdio.h>
#define N 1100
int v[N],min[N],max[N],min_coins[N],max_coins[N];
void print_ans(int *d,int s, int n) {
while(s){
printf("%d ",v[d[s]]);
s-=v[d[s]];
}
printf("
");
}
int main() {
int T,i,j,n,s;
scanf("%d",&T);
while(T--) {
scanf("%d %d",&n,&s);
for(i=0;i<n;i++)
scanf("%d",&v[i]);
min[0]=max[0]=0;
for(i=1;i<=s;i++){
min[i]=0x7FFFFFFF;
max[i]=-0x7FFFFFFF;
}
for(i=1;i<=s;i++){
for(j=0;j<n;j++){
if(i>=v[j]){
//min[i]=min[i]<(min[i-v[j]]+1)?min[i]:(min[i-v[j]]+1);
if(min[i]>min[i-v[j]]+1){
min[i]=min[i-v[j]]+1;
min_coins[i]=j;
}
if(max[i]<max[i-v[j]]+1){
max[i]=max[i-v[j]]+1;
max_coins[i]=j;
}
//max[i]=max[i]>(max[i-v[j]]+1)?max[i]:(max[i-v[j]]+1);
}
}
}
printf("%d %d
",min[s],max[s]);
print_ans(min_coins,s,n);
print_ans(max_coins,s,n);
}
return 0;
}上のコードでは、出力パスが不要な場合はmax_coinsとmin_coins配列、次は再帰的なものを書きます.
#include<stdio.h>
#include<string.h>
#define N 1100
int v[N],d[N],vis[N];
int dp(int s, int n) {
int i;
if(vis[s])
return d[s];
vis[s]=1;
d[s]=-1<<30;//
for(i=0;i<n;i++)
if(s>=v[i]&&d[s]<dp(s-v[i],n)+1)
d[s]=dp(s-v[i],n)+1;
return d[s];
}
void print_ans(int s,int n){
int i;
for(i=0;i<n;i++){
if(s>=v[i]&&d[s]==d[s-v[i]]+1){
printf("%d ",v[i]);//
print_ans(s-v[i],n);
break;
}
}
}
int main() {
int T,i,n,s,ans;
scanf("%d",&T);
while(T--) {
scanf("%d %d",&n,&s);
for(i=0;i<n;i++) {
scanf("%d",&v[i]);
}
memset(vis,0,sizeof(vis));
vis[0]=1;
d[0]=0;// 0，
ans=dp(s,n);
printf("%d
",ans);
print_ans(s,n);
printf("
");
}
return 0;
}最長経路を求めるもののみを記載しており、最短経路が要求される場合は最長経路と類似しており、ここでは省略する.